The standard Turing Machine (TM) can only move left and right. When I simulate a TM whose head may remain stationary and I execute the stationary move, then I need to make two steps with the standard TM: go left and then right. So does this mean I need twice the amount of steps and I need twice the amount of states?


Twice the amount of steps and twice the amount of states suffice for the simulation.

The sketch is as follows: replace every transition of the original TM that keeps the head still and changes the state to $q$ with two transitions: first move the head right and change the state to a new intermediate state $q'$, then whenever the state is $q'$ move the head left (without modifying the current tape symbol) and go to state $q$.

You can actually construct an equivalent TM that uses at most one more state and requires at most the same number of steps. The sketch is as follows: consider a transition of the original TM that keeps the head still. This transition writes $\alpha$ to the current tape cell and changes the state to $q$. Then you can find the next transition that will be executed by the machine, i.e., the transition performed when the current tape symbol is $\alpha$ and the current state is $q$. Suppose that the latter transition writes $\beta$ and moves to $q'$. If the transition also moves the head, then you can "shortcut" the first transition by directly writing $\beta$ and moving to $q'$.

If the second transition does not move the head, then the process can be repeated. Eventually (there are at most $|\Gamma| \cdot |Q|$ distinct transitions that can be applied, where $\Gamma$ is the tape alphabet) you either reach a transition that moves the head/halts the machine, or you discover that the machine must loop.

In the former case you can shortcut all involved transitions to the last one. In the latter case, you can add only a single (global) additional state to ensure that the machine runs forever while moving its head.


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.