How to insert symbols into tape?

Question

I have this problem. The input alphabet is $\{A, B\}$ and I should design a machine that converts a single $A$ into $AC$. That is, a string like $ABAB$ should become $ACBACB$. This means that there are cases where I have to memorize what is read from the tape, while simultaneously writing something else. As far as I can understand, memorizing translates into entering in a state telling me what I have just read, and what I need to actually write. Following these assumptions, the states should be:

• I read a symbol and I write it down immediately
• I read a symbol and I memorize it writing down something else

I can expand the states and design all the transitions, but nonetheless, I am not able to obtain a working machine.

What is the correct approach to the problem of memorization?

Thanks in advance.

Answer 1

Sketch:

1. Start at the left hand side of the string and read until you find the first $A$.

2. Change the $A$ to another character, such as $\#$.

3. Go to the end of the string and, one-by-one (and backwards), shift characters one step to the right.

4. When you reach $\#$, replace it with $AC$ and continue reading to the right.