Does every turing machine have an equivalent, single-state, n-tape turing machine?

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

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.

StackExchange Computer Science Q#75161, answer score: 12