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.)
$\begingroup$
$\endgroup$
5
-
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üttelMay 9, 2017 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 MeierMay 9, 2017 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, 2017 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 BauerMay 9, 2017 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 RicherbyMay 10, 2017 at 10:28
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
On all the comments:
Usually a TM is used to compute something, e.g. a yes/no about word \in language. Therefore, either we are nit-picking and require at least two halting states (accept, reject) PLUS one start/working state (although 2 states are usually considered sufficient for completeness for a singel-tape TM)... ... or the answer is in the final tape contents, and we stop e.g. by running off to the left (for a mono-infinite tape) or writing, then reading a symbol that incurs undefined behaviour - and the tape says "Nay" or "Yeah" (symbols abound).
As far as the completeness is concerned, Ben I. makes the point: Yes, the state can be completely moved out of the FSM onto the 2nd tape.
The essential point is the independence of the two read/write heads and the option to not move the head at all.
