5
$\begingroup$

Is it the case that every problem computable by a Turing Machine can also be represented by some kind of equivalent n-tape Turing Machine which one has only one state? (We can assume that the accept and reject states are implicit here. If that bothers you, you may think about this as a question about 3-state machines instead.)

$\endgroup$
  • 2
    $\begingroup$ Every Turing machine must have at least an accept state and a reject state, and these must be distinct -- so the answer is no. And how is the computable problem related to the Turing machine? This is not clear at all from the question. $\endgroup$ – Hans Hüttel May 9 '17 at 16:27
  • $\begingroup$ I just added "computable" because I thought this is cleaner. The question could be changed to "Is it for every 1-tape turing machine possible to reduce it to a n-tape turing machine with 1 state?". But as you already explained it isn't. But then I think it should be possible to always construct a 2-tape turing machine? $\endgroup$ – Kevin Meier May 9 '17 at 17:46
  • $\begingroup$ Using his logic, I believe you're asking about a 3-state machine (start, accept, and reject) $\endgroup$ – Ben I. May 9 '17 at 17:51
  • $\begingroup$ This question does not make sense. You should at the very least require that the $n$-tape single-state machine behave equivalently to the original machine. But then you have to define "behave equivalently". $\endgroup$ – Andrej Bauer May 9 '17 at 18:52
  • $\begingroup$ The edit seems clear enough. A TM with only one state other than the accept/reject state is a very simple kind of one-dimensional cellular automaton. Whenever it sees a particular character, it always behaves the same way: it either replaces it with some specific character and moves left, replaces it and moves right, accepts, or rejects. Presumably somebody who knows about cellular automata can come along and tell us that this class of automata isn't Turing-complete. $\endgroup$ – David Richerby May 10 '17 at 10:28
10
$\begingroup$

Yes, there always exists a machine, and we really only need 2 tapes.

Your standard TM transition might be written:

$\delta(S_n, a) = (S_m, b, r)$

This would mean that, from $S_n$, if we read $a$, we would write $b$, move in direction $r$, and transition to state $S_m$. We will allow our machine to move left, right, or stay in place ($<$, $>$, or $-$).

Now for the 2-tape machine, we'll go to our infinite shelf of Turing Machines and grab a standard two-tape model where both heads have independent left/right/stay capabilities.

As it turns out (just our luck!), on this machine, one of the motors actually broke a few years ago, so the second head can still read and write, but it can't move left or right any more. Not to fear, we won't be needing that motor. This machine will serve our needs just fine.

This model happens to be called the TwoTapey. On the TwoTapey, we could write a transition this way:

$\delta(S_n, a_1, a_2) = (S_m, b_1, b_2, d_1)$

This transition would mean that, from $S_n$, if the TwoTapey reads $a_1$ on tape 1 and $a_2$ on tape 2, it would transition to $S_m$, write $b_1$ on tape 1, $b_2$ on tape 2, and move head 1 $d_1$. On a normal two-tape TM, we'd need a $d_2$ for the second head, but there's no need for that here, because that darned motor is still busted.

So, to translate our standard TM to the TwoTapey, we need to add each of our original state names as strings into the tape alphabet of the 2-tape machine. Then, take each transition, and translate it this way:

$\delta(S_n, a) = (S_m, b, r)$

becomes

$\delta(S_0, a, ``S_n") = (S_0, b, ``S_m", r)$

The key is that busted motor. Since we never move left or right on the second tape, this allows us to imitate our original states by simply using the second tape to hold our old state information. This allows us to transition from $S_0$ back to $S_0$, but still utilize just as many transitions as we used to have in the original machine.

As CandiedOrange pointed out to me, this is actually a really good way to show that the hardware/software divide is artificial. All state is just data, and all data is just state.

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