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

Question

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.

Answer 1

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

Answer 2

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$.