-1
$\begingroup$

I read in some text book ( either ullman or peter linz) that a turing machine must have at least two states. I don't understand why?

For example if we want to build a Turing Machine for the empty language then we can start in state $q_o$ (accept state). We will define only one transition for epsilon on which the input would be accepted. However if the input is something else then since we have not defined any transition we would enter dead configuration.

what's the problem with this approach?

$\endgroup$
  • 1
    $\begingroup$ Could you provide more detailed information, e.g. which book and page number? $\endgroup$ – fade2black Jan 10 '18 at 19:20
2
$\begingroup$

Under most definitions, a Turing machine can have only one state. Maybe the authors of the book wanted to require at least two states because it makes their presentation easier for some reason.

Small details like this are irrelevant when it comes to complexity theory. We are not interested in the "implementation details" of our model of computation.

$\endgroup$
  • $\begingroup$ By "only one state", do you mean "only one current state", or "only one state in the total state-space"? The first makes sense, but I think OP is talking about the second. $\endgroup$ – jmite Jan 10 '18 at 21:40
  • $\begingroup$ @jmite Only one state in the total state space. $\endgroup$ – David Richerby Jan 10 '18 at 22:31
2
$\begingroup$

TL;DR: technically, there need to be an accepting and rejecting state and they need to be different; but it's not a big deal and, at an intuitive level, one-state machines work just gine.


A Turing machine is typically defined to be a tuple $M=\langle Q, \Sigma, \Gamma, \delta, q_0, q_\mathrm{acc}, q_\mathrm{rej}\rangle$ where the items are the state set, input and tape alphabets, the transition function (or relation for a nondeterministic machine), and the initial, accepting and rejecting states, respectively.

The accepting and rejecting states must be distinct because the machine cannot simultaneously accept and reject. Therefore, there must be at least two states.

In principle, you might want to define a Turing machine that has only one state: the initial state would be the accepting state and there'd be no rejecting state, or vice-versa. There's nothing morally wrong with that but it would make the definition more complicated. Instead of saying "A Turing machine has distinct accepting and rejecting states", you'd have to say "A Turing machine either has distinct accepting and rejecting states, or it has just one state which is either the accepting state or the rejecting state." That's more complex, and it doesn't buy you anything, so people don't do it.

But note that this isn't really an important point. You can perfectly well think of Turing machines with just one state and it won't hurt you in any way, unless you try to write down a formal definition. Any machine that you want to think of as having one state, you can easily rewrite as having two states: just add the second state, which will be inaccessible.

$\endgroup$
0
$\begingroup$

Possibly you are remembering that, while there are computable functions that cannot be computed by a one-state machine, every computable function can be computed by a machine with two states? (This maybe should be a comment but I lack the reputation.)

$\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.