5
$\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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Closely related questions: 1, 2. $\endgroup$
    – Raphael ♦
    Jun 29, 2015 at 20:46

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\endgroup$
2
  • 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, 2015 at 20:12
  • $\begingroup$ @Gravity Exactly. $\endgroup$
    – David Richerby
    Jun 29, 2015 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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