3
$\begingroup$

When we consider multi-tape Turing machines, we can assume that each tape is accessed with a separate head and each head can move independently of the other heads. But can we assume that each tape can be in its own state independently of the other tapes (for example, tape 1 in state A, tape 2 in state F, tape 3 in state X simultaneously)?

Then, for example, the table of instructions for some three-tape two-symbol ("0" and "1") machine can look like this:

    | 000         | 001         | ...
----------------------------------
AAA | 011/BXZ/LRL | 010/XYB/RRR | ...
----------------------------------
AAB | 001/TSH/LLR | 110/AET/LLL | ...
----------------------------------
...

where the first cell of the table can be interpreted as follows: if the first tape is in state A, the first head is over the cell with symbol 0, the second tape is in state A, the second head is over the cell with symbol 0, the third tape is in state A, the third head is over the cell with symbol 0, then the first head writes "0" instead of "0", then the first tape goes into state B, then the first head moves to the left, then the second head writes "1" instead of "0", then the second tape goes into state X, then the second head moves to the right, then the third head writes "1" instead of "0", then the third tape goes into state Z, then the third head moves to the left.

$\endgroup$
2
$\begingroup$

Yes. You can equivalently transform such multi-state multi-tape Turing machine to a normal multi-tape Turing machine where each state in the new Turing machine represents a combination of states in the multi-state multi-tape Turing machine.

For your example, you can encode state "AAA" into state 1, state "AAB" into state 2, and so on (so there are in total $26^3$ states). Now it becomes a normal multi-tape Turing machine.

$\endgroup$
4
$\begingroup$

A Turing machine has just one state, even if it has multiple tapes. If you give each tape a separate state, it’s easy to forget that the action of each tape head can depend on the global state and on the character under every head, which is crucial, because it is the only way the tapes can communicate with each other. A multi-tape TM is a single computer with multiple I/O devices, not multiple computers each with one I/O device.

xskxzr’s answer shows that one state per tape doesn’t actually change the computational power of Turing machines. But it’s important to note that this requires the actions of all tape heads to be allowed to depend on every tape’s state and every tape’s current character. Thinking about each tape having its own state is likely to make you forget this, resulting in a less powerful machine. Conceptually, it’s usually not a good way to think about Turing machines.

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