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?


2 Answers 2


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.

  • $\begingroup$ Thank you very much, sir. You have given wonderful explanations. $\endgroup$
    – A Paul
    Commented Oct 4, 2020 at 17:08
  • 3
    $\begingroup$ For fun, Manufactoria is a crazy TM variant. $\endgroup$
    – user21820
    Commented Oct 4, 2020 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$ Commented Oct 4, 2020 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
    Commented Oct 4, 2020 at 22:45

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.


Your Answer

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

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