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.