patternMinor
For multi-tape Turing machines, can we assume that each tape can be in its own state independently of the other tapes?
Viewed 0 times
assumecanthemultieachindependentlyitstapethatfor
Problem
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:
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#90154, answer score: 4
Revisions (0)
No revisions yet.