Re: Turing Machine
- From: Patricia Shanahan <pats@xxxxxxx>
- Date: Sun, 25 Feb 2007 19:31:28 GMT
meyousikmann wrote:
A Turing machine with fast-forward (FFTM) works like a normal Turing machine except that its transition function outputs one of three directions to move the head: L moves the head one space to the left, R moves the head one space to the right, and FF moves the head twice as far as its current distance from the beginning of the tape (if tape head is on the second tape space, FF will move the head to the fourth tape space).
I am told that there is an ordinary TM (without FF) that will recognize the same language as the FFTM. I would like to prove that this is so, but am not sure how to do that. Any ideas where to start?
I've generally found extended TM questions easier to solve using a
multi-tape TM, with a fixed set of extra tapes dedicated to supporting
the extension.
Patricia
.
- References:
- Turing Machine
- From: meyousikmann
- Turing Machine
- Prev by Date: Re: On the General Construction for Kleene star in Context-Free Language
- Next by Date: An efficient way of sequencing streams of integers
- Previous by thread: Turing Machine
- Next by thread: An efficient way of sequencing streams of integers
- Index(es):
Relevant Pages
|
