This turing machine duplicates a string of 1's. Specifically, if q is the initial state and f is the final state, then the machine operates as... q00w |-*- f0w0w (replace the last 0 with 0w) and then, q0w0w |-*- f0ww0w where w is a string of 1's. Method: Mark the rightmost 1 with an x, go left and replace the leftmost 0 with 01. Repeat until all 1's in the rightmost w are x's. Then replace all x's with 1's, go to left end of tape and halt. States: {0,1,2,3,4,5,7,8,9} (there is no state 6) Final state: {9} Alphabet: {0,1} ------------------------------------------------------- (0000r state 0: to start off, find the right end (0110r (0xx0r some 1's may have already been marked (0 2l state 2: found the right end. Mark the last 1 with an x (2xx2l move past already marked locations. !(21x3l (2007r state 7: No more 1's to duplicate, change x's back to 1's (21x3l state 3: duplicate the 1 that was just marked... move left to find the leftmost 0 (3113l (3003l (3xx3l (3 4r state 4: found the front of the string. Add a 1. (4015l state 5: add a terminating 0 (5 00r state 6: now go to the right end of string and repeat (7x17r (7 8l state 8: move to left end and halt. (8008l (8118l (8 9r state 8: final state