Copy operation in under 9 states?
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