- #1

0rthodontist

Science Advisor

- 1,230

- 0

A paper tape Turing machine (PTM) is a Turing machine whose tape alphabet is partially ordered, and if a is a symbol on a square of the tape, then b can only be written on that square if b is greater than a in the partial order. Show that a PTM can simulate T steps (tape head movements/writes) of a one-tape Turing machine in O(T^2) steps.

O(T^3) is easy, you can just copy the whole tape over again at every step for O(T^2) PTM steps at step T of the TM.

To get O(T^2) the PTM head can't move more than O(T) steps at a given step T of the TM, which means it can move back and forth over the PTM tape at most a constant number of times on average per step of the TM. When you need to change a symbol on a tape square in the wrong direction, the natural thing to do is go to the right or to the left until you have an empty square, and write the new symbol. If this could be made to work, it would be T^2 time. But I don't see how to maintain the association between the new symbol and the old square.