I am going to design a Turing machine for doubling any words. My algorithm is such that for word X as input, the output will be in the form X@X which @ is a character. How can design an one-tape Turing machine that give exactly XX as its output? For example, X=abba, XX=abbaabba. Thank you in advance for consideration.
Design a Turing machine $T$ that takes as an input a word with an unique occurrence of the "@" symbol and shifts all symbols after "@" one position to their left (thus overwriting "@" and replacing the last symbol of the word with the blank symbol).
This can be done by finding the end of the input word, setting the machine state to store the "blank" symbol, moving to the left, and then iteratively performing the following step:
- simultaneously store the current symbol in the machine state, write the stored symbol on the current cell of the tape, and move left.
The above repeats until the read symbol is "@". When that happens the stored symbol is written in place of "@" and the machine halts.
Compose the Turing machine you already designed with $T$.