# How would you create a Turing machine that copies a string and prints it to the tape?

For example, if I have a start state of $i$ and a string $w$, how could I create a Turing machine that would halt when the tape content is $w \Box w$? The language is $\{a,b\}$.

My initial idea was a machine that:

On $i$, moves right and changes to $p$.

On $p$, if letter read is $a$, move $n+1$ cells to the right and change to $x$.

On $p$, if letter read is $b$, move $n+1$ cells to the right and change to $y$.

On $p$, if $\Box$, change to $h$.

On $x$, write $a$, move $n$ cells to the left and change to $p$.

On $y$, write $b$, move $n$ cells to the left and change to $p$.

On $h$, halt.

However, I don't think it'll work because Turing machines aren't allowed to move more than 1 cell at a time. Any help would be appreciated.

You are pretty close, here is a TM deciding the language (pseudocode):

1. Check the input contains a single $\Box$,

• If false, reject.
2. Zig-zag across the tape, check identical letters, and replace them by $X$.
• If not identical, reject.
3. When all the letters left of $\Box$ are marked $X$, check for remaining letters right of $\Box$
• If there are remaining letters, reject.
• Otherwise, accept

How can you move exactly $$n+1$$ squares? Put a special mark at the end before you leave, then move back to the mark.

How can you remember which character to copy? You have a finite alphabet, so duplicate the states you use for each character. For example, you'll be in $$p_a$$ when copying character $$a$$ and in $$p_b$$ when copying character $$b$$.