Copy operation in under 9 states? There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following graphic the machine is denoted by a yellow line. It is immediately to the right of a series of three 1’s followed by many 0’s.



The machine is tasked to make a copy of the 1’s. When finished, the copy must be separated from the original by a single cell containing a 0. The final resting place for the machine is immediately to the right of the original 1’s. The following graphic shows the cells after the machine has fulfilled its copy task.



At each step the machine must decide whether to move left one cell or right one cell, and whether to write 0 or 1 to the cell that it is currently positioned at. The machine cannot see what is in the neighboring cells. It can only see the value in the current cell. The machine makes its decision based purely in the current cell’s value and on the decisions it made previously. 

I was able to program the machine to perform the copy operation using nine states (S0 – S8). 

QUESTION: Is there a way for the machine to perform the copy operation in less than nine states? 

The above graphics show just one example, in which three 1’s are copied. Of course, the machine must be able to perform the copy operation on any number of 1’s.

The diagram below shows the nine states that I needed. But first, here is an explanation of a notation used in the diagram:



Here is the strategy I used: As described above, the 1’s must be copied. How to know which 1’s have been copied and which remain to be copied? Answer: Shift the leftmost 1 to the left one cell and then copy it. Repeat for the next leftmost 1. And so on. There will be a series of shifted 1’s that have been copied and a series of unshifted 1’s that remain to be shifted and copied. Once there are no more unshifted 1’s, the machine is done. State 0 is the final state. State 1 is the starting state.
Input: 0^a 1^b 0^c with a + c >= b + 1

Output: 0^z 1^b 0 1^b with b + z + 1 = a + c

Strategy:


Move 1^b to the back of the tape
Copy 1^b immediately to the left
Clean up


States:


q0: scan left until you see 1; if beginning of tape, continue with state q3. Otherwise, change 1 to 0 and continue to q1
q1: scan right until blank or 1; then, move left and continue with state q2
q2: change 0 to 1, go left, and continue with q0
q3: scan right until you find 1; if you do, change 1 to 2, move left and continue with step q4; otherwise continue with state q6
q4: scan left until you find 0; then, move right and continue with state q5
q5: scan left until you find 0; when you do, change it to 2, move right, and continue with state q3
q6: scan left until you find a blank, changing all 2s to 1s along the way. then, halt-accept.


If you count halt-accept as its own state, this has 8 states, so it's at least one better than the one you gave (if this one works). Here's how I'd see it processing your example:

   0000001110: q0
-&gt; 0000001101: q0, q1, q2, q0
-&gt; 0000001011: q0, q1, q2, q0
-&gt; 0000000111: q0, q1, q2, q0
-&gt; 0000020211: q0, q3, q4, q5, q3
-&gt; 0000220221: q3, q4, q5, q3
-&gt; 0002220222: q3, q4, q5, q3
-&gt; 0001110111: q3, q6, halt-accept