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) 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,6,7,8,9,a} Final state: {a} Alphabet: {0,1} ------------------------------------------------------- (0000r state 0: to start off find w (0111r state 1: once in w, get to the right end (1111r (1 2l state 2: found the right end. Mark the last 1 with an x (21x3l state 3: duplicate the 1 that was just marked... move left (3113l entering in turn states 4, and 5 to do so (3004l state 4: have gone past the rightmost dividing 0. (4114l going past 1's that have already been duplicated. (4015l state 5: just replaced the leftmost 0 with 1, now (5 06r add a leftmost 0. ---------- now repeat.... (6116r state 6: move to the right to repeat (6007r state 7: moved onto the rightmost w. Test it... (7111r ....There are 1's left to duplicate (1xx2l found the right end. Mark the last 1 with an x by looping back up to the (21x3l) quintuple above ....There are no more 1's left, so (7x18r state 8: All the 1's were already marked. Change x's back to 1's (8x18r (8 9l state 9: Move to left end and halt (9119l (9009l (9 ar state a: Final state