3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Closely related questions: 1, 2. $\endgroup$ – Raphael Jun 29 '15 at 20:46
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ okay I understand, but that means, when you are designing the transition function, you need to add a state for every single letter you would like to remember, is that right? $\endgroup$ – Gravity Jun 29 '15 at 20:12
  • $\begingroup$ @Gravity Exactly. $\endgroup$ – David Richerby Jun 29 '15 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.