When illustrating what states are in Turing machine, often the examples of programs, like a checker that checks an input number is even number, are given. But different programs seem to have different number of states - if so, how can Turing machine be described with the set of finite number of states, along with others? In other words, if we follow the formal definition of Turing machine, can we construct a state diagram of a Turing diagram, assuming infinite memory exists?
1 Answer
$\begingroup$
$\endgroup$
6
There are two possible meanings of state here:
One of the finite states in the finite control mechanism of the Turing machine.
The entire state of the Turing machine, including its internal state (the one from the previous definition), the locations of the heads, and the contents of the tapes.
If you are looking for a state diagram of the second type, then it's infinite. If you're looking for a state diagram of the first type, then it's finite.
Different programs seem to have different number of states – every program is finite (has finitely many states, under the first interpretation above), but there is no bound on its length: it can be as long as you want, as long as it's finite. The same is true for Turing machines.
answered Nov 5, 2014 at 3:17
-
$\begingroup$ I was thinking about the first definition. So Turing machine does not have a fixed number of states? This seems weird, because the formal definition of Turing machines talk about having a set of finite number of states. Is it just saying that depending on a program the number of states can change, but has to be finite? $\endgroup$– elpsNov 5, 2014 at 3:20
-
$\begingroup$ It's like the example of a C program (or pick your favorite programming language). We insist that the program is finite, but it can be as long as we want. Or take numbers – every integer can be written as a string of digits; the string has to be finite, but it can be as long as we wish. $\endgroup$ Nov 5, 2014 at 3:21
-
$\begingroup$ Each Turing machine corresponds to a different program. There are many (in fact, infinitely many) different Turing machines. $\endgroup$ Nov 5, 2014 at 3:22
-
$\begingroup$ But then there is a universal Turing machine that can simulate all other Turing machines.... So what would this mean for the number of states? $\endgroup$– elpsNov 5, 2014 at 3:28
-
$\begingroup$ The universal Turing machine accepts as input an encoding of a Turing machine and an input, and runs the Turing machine on the input. That just moves the program from the control of the Turing machine to its initialization. You can also probably convert any Turing machine to one that uses a constant number of states but an unbounded tape alphabet. $\endgroup$ Nov 5, 2014 at 3:30