patternMajor
What are the options of head movement for a Turing machine?
Viewed 0 times
thewhatareheadoptionsmovementformachineturing
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#130784, answer score: 20
Revisions (0)
No revisions yet.