1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

There are two possible meanings of state here:

  1. One of the finite states in the finite control mechanism of the Turing machine.

  2. 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.

$\endgroup$
6
  • $\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$
    – elps
    Nov 5 '14 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 '14 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 '14 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$
    – elps
    Nov 5 '14 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 '14 at 3:30

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.