1

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.

Miagu
  • 13
  • What you describe can, potentially, work. Could you provide details about how you're creating your machine? – Michael Burr Jan 03 '18 at 15:31
  • I only have some non working draft. The problem I was facing was what to do when insertions were accumulating. That is, finding an $A$ after an $A$, the number of the states exploded. Still, I think it's more of a problem of how to "turing-ize" the problem. – Miagu Jan 03 '18 at 16:34

1 Answers1

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.

Michael Burr
  • 32,867
  • This! I appreciate the way you approached the problem, I was drowning myself with my approach. Thanks:) – Miagu Jan 03 '18 at 16:28
  • Your approach can also work, you just need to remember the last two characters that you read (so you'll need about 6 states to move everything one step down the line). It's easier to always be writing into a blank space. – Michael Burr Jan 03 '18 at 16:31