5
$\begingroup$

I find several contradictory definitions regarding the head movements of the Turing machine. In some places, it is only L / R. While in some other formal definition; it is L / S / R. Which one is correct?

$\endgroup$
19
$\begingroup$

You are right to be confused! The problem is that different authors disagree on the definition of a Turing machine. There is actually no one "right" answer. Some authors define that the machine moves L / R; but others define that it moves L / S / R, as you have pointed out.

This is not the only thing that different definitions of a Turing machine disagree on. For example, some authors say that a Turing machine has a "halt" state, and some say that it has an "accept" and a "reject" state. Additionally, some authors say that a Turing machine's tape is "doubly infinite", meaning that it extends to infinity in both directions. But other authors say that a Turing machine's tape is "singly infinite", meaning that it only extends to infinity in one direction, and in the other direction it stops.

So what should you do about this? Well...

  • If you are a student or learning from a book: take a look at your textbook to see which definition they use. That definition is the "correct" one for the purposes of working through specific exercises.

  • If you are trying to understand the "bigger picture": then realize that it actually doesn't matter which definition you use! It turns out that all the different definitions are equivalent. So, which definition is picked is more a matter of convention, kind of like how we choose to say that $1$ is not a prime number, even though historically many mathematicians said that it was.

  • If you a researcher: Just pick whichever one is convenient to you or makes sense to you, and stick to it, and make sure you are consistent within your own paper or writing material to always use the same definition.

Which one is correct?

To reiterate: neither is correct; they are just different conventions. It doesn't really matter which you pick, because it turns out they are all equivalent.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much, sir. You have given wonderful explanations. $\endgroup$ – A Paul Oct 4 at 17:08
  • 3
    $\begingroup$ For fun, Manufactoria is a crazy TM variant. $\endgroup$ – user21820 Oct 4 at 17:24
  • 3
    $\begingroup$ I think this answer could be improved by addressing some examples of equivalencies (how a machine with L/R movement is equivalent to one with L/S/R) either by presenting proof sketches or providing some links. $\endgroup$ – potestasity Oct 4 at 22:19
  • 2
    $\begingroup$ Indeed the fact that they are all equivalent is one of the most profound proofs in all of computer science. $\endgroup$ – Cort Ammon Oct 4 at 22:45
0
$\begingroup$

As explained, the two formalisms are equivalent, as well as many other variations of Turing machine formalisms, so in a sense it doesn't matter.

But, if you want to 'program' a Turing machine, if you are using a single-tape machine, I guess having S is okay but kinda pointless: at some point you should move your head, so why don't you do that right now?

On the other hand, if you are using a multi-tape machine, having S could be useful: you can do something on one tape, while other heads on other tapes remain stationary.

| cite | improve this answer | |
$\endgroup$

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.