[Math] If in a turing machine, whenever the head tries to move left, it gets rewinded all the way to the leftmost cell.

computational complexityformal-languagesturing-machines

ASSUMPTION : Turing Machine has one sided infinite tape(right to be precise).

Given following constrained (deterministic single-tape) Turing Machine, what is the class of language recognized by it.

Restraint:

The Turing machine, on each transition can perform three operations(wrt moving L,R,S)

1.) It can move right by one cell.

2.) It can stay on current cell.

3.) It can move to the leftmost cell. (restraint)

So Does this turing machine accepts all the languages accepted by a Unrestrained turing machine or not.

I think it accepts all that an unrestricted turing machine can accept, but I am still doubtful.

Best Answer

This type of machines is indeed equivalent in power to ordinary Turing machines. In fact, even if you remove the ability to perform the second type of moves (stay on the current cell), the power of the machine will not be affected. Here is how such a restricted TM can be converted to an unrestricted one.

When the machine needs to move the head to the right, it first puts a special mark, e.g. $\sim$, upon the current symbol. Then it goes all the way back to the leftmost cell, and starts moving rightward. While the machine does so, if another special mark, e.g. $\bullet$, is discovered on a symbol, it gets removed from it. Once the head encounters $\sim$, the machine replaces it with $\bullet$ and moves the head one cell to the right. This combination of moves is equivalent to one move to the right performed by an ordinary TM. Note that the symbol in the left adjacent cell is now marked with $\bullet$.

When the head needs moving to the left, there are three possibilities.

  1. The head points to the leftmost cell. In this case the tape contains no symbols marked with $\bullet$.
  2. The head points to the cell adjacent to the leftmost cell. In this case the tape does contain a symbol marked with $\bullet$, which is located in the leftmost cell.
  3. The head points to neither the leftmost cell nor its adjacent cell. In this case the tape also contains a symbol marked with $\bullet$, which is not in the leftmost cell. This is the symbol the head needs to move to.

The first case can be handled by marking the current symbol with $\sim$, moving the head to the leftmost cell and checking if the current symbol has $\sim$ upon it. If it does, remove it and remain in this cell, the move is now complete. Otherwise, check if the current symbol has $\bullet$ upon it. If it does, remove it, move the head to the adjacent cell, remove $\sim$ from the symbol in that cell and move to the leftmost cell again. This handles the second case. To deal with the last case perform the following steps.

  1. Mark the current symbol with $\bullet$.
  2. Move the head one cell to the right.
  3. Check if the current symbol is marked with $\bullet$.
    • If it is, remove $\bullet$, move the head one cell to the right, remove $\sim$, move the head to the leftmost cell and scan the tape for an occurrence of $\bullet$. Once it is found, move the head one cell to the right and finish.
    • Otherwise, put $\bullet$ upon it, move the head to the leftmost cell and scan the tape for the first occurrence of $\bullet$. Once it is found, remove it, move the head one cell to the right and proceed with step 2.

This simulates one move leftward performed by an ordinary TM. Note, that unless the head is pointing to the leftmost cell, the symbol in the left adjacent cell is marked with $\bullet$.

Related Question