1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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

step-Right 

while the current character a is not a space
do
    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
    step-Right
od

move-Right until space
Improve this answer
$\endgroup$

Your Answer

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

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