I am using the book Elements of the Theory of Computation (2nd edition), which has been fine until now. However, I am stuck trying to grasp the Machine Turing conveyed in Example 4.1.8 (pages 189-190). I cannot make sense of the copying machine portrayed in Figure 4-8. Can someone help me understand with an input word as an example?

enter image description here


1 Answer 1


The following is how I decode this program. The $R_\sqcup$ is a macro for the machine that moves right until it reads a blank. I deduce that $R^2_\sqcup$ repeats this process, locating the second blank to the right. Now the machine shutles right and left moving one non-blank $a$ to the right each cycle.
The position in the original string of the current copied character is temporarily marked with a blank.

move-Left until space


while the current character a is not a space
    write space // overwriting a, but it is memorized,
    twice: move-Right until space,
    write a       //on the position of the second space
    twice: move-Left until space,
    write a       // restoring the a in the first copy

move-Right until space

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.