patternMinor
The control in the Turing Machine
Viewed 0 times
turingthecontrolmachine
Problem
My question is about the control in the Turing Machine. As far as I know, the control of the Turing Machine is just a set of states. If the Machine needs to record something, it needs to write on the tape.
The following is an excerpt from Michael Sipser's Theory of Computation, the passage is about how a Turing Machine can find the leftmost Cell. What is written is pretty straight forward. But what I don't understand is the part written in bold.
"A trickier method of finding the left-hand end of the tape takes
advantage of the way that we defined the Turing machine model. Recall
that if the machine tries to move its head beyond the left-hand end of
the tape, it stays in the same place. We can use this feature to make
a left-hand end detector. To detect whether the head is sitting on the
left-hand end, the machine can write a special symbol over the current
position while recording the symbol that it replaced in the control.
Then it can attempt to move the head to the left. If it is still over
the special symbol, the leftward move didn’t succeed, and thus the
head must have been at the left-hand end."
What does he mean by this exactly? What does recording a symbol in the control mean? Isn't the only (and infinite) memory of the TM the tape?
The following is an excerpt from Michael Sipser's Theory of Computation, the passage is about how a Turing Machine can find the leftmost Cell. What is written is pretty straight forward. But what I don't understand is the part written in bold.
"A trickier method of finding the left-hand end of the tape takes
advantage of the way that we defined the Turing machine model. Recall
that if the machine tries to move its head beyond the left-hand end of
the tape, it stays in the same place. We can use this feature to make
a left-hand end detector. To detect whether the head is sitting on the
left-hand end, the machine can write a special symbol over the current
position while recording the symbol that it replaced in the control.
Then it can attempt to move the head to the left. If it is still over
the special symbol, the leftward move didn’t succeed, and thus the
head must have been at the left-hand end."
What does he mean by this exactly? What does recording a symbol in the control mean? Isn't the only (and infinite) memory of the TM the tape?
Solution
The state of the machine can be used as a finite memory. You can use the state to remember (or, if you prefer, "encode") what the last character you saw was, since there are only finitely many possibilities. If necessary, you can remember the last two characters, or ten or a million, as long as you fix the number at the time when the machine is designed.
What you can't do is remember an unbounded amount of information in the state. So you can't remember, for example, all the characters you've passed over since you last saw an '$a$', or even the number of characters since then.
What you can't do is remember an unbounded amount of information in the state. So you can't remember, for example, all the characters you've passed over since you last saw an '$a$', or even the number of characters since then.
Context
StackExchange Computer Science Q#44045, answer score: 8
Revisions (0)
No revisions yet.