Suppose I have the following subroutine, to a more complex program, that uses spaces to the right of the tape:

$A$: "adds a $ at the beginning of the tape."

So we have: $$ \begin{array}{lc} \text{Before }: & 0101\sqcup\sqcup\sqcup\ldots\\ \text{After }A: & \$0101\sqcup\sqcup\ldots \end{array} $$

And it is running on a multi-tape turing machine. The equivalence theorem from Sipser book proposes we can describe any multi-tape TM with a single-tape applying the following "algorithm", append a $\#$ at every tape and then concat every tape in a single tape, and then put a dot to simulate the header of the previous machine, etc, etc.

With $a$ and $b$ being the content of other tapes, we have: $$ a\#\dot{0}101\#b $$ If we want to apply $A$ or another subroutine that uses more space, the "algorithm" described in Sipser is not enough, I can intuitively shift $\#b$ to the right, but how to describe it more formally for any other subroutine that uses more space in the tape? I can't figure out a more general "algorithm" to apply in this cases.


Sipser's book handles this case:

If at any point $S$ moves one of the virtual heads to the right onto a $\#$, this action signifies that $M$ has moved the corresponding head onto the previously unread blank portion of that tape. So $S$ writes a blank symbol on this tape cell and shifts the tape contents, from this cell until the rightmost $\#$, one unit to the right. Then it continues the simulation as before.

  • $\begingroup$ Thank you, I had a wrong interpretation when I first read this. $\endgroup$ – Jader Martins Oct 2 at 3:40

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.