CIT 594 Turing Machine example
Spring 2012, David Matuszek

Here is the completion of the example we started in class.

δ (the transition function) Trace
start 0 0 R start
start 1 1 R start
start - - R start
start # # L dup

dup 1 1 R put1
dup 0 0 R put0
dup - - R put-

put1 0 1 L back
put1 1 1 L back
put1 # 1 L back
put1 - 1 L halt

put0 0 0 L back
put0 1 0 L back
put0 # 0 L back
put0 - 0 L back

put- 0 - R halt
put- 1 - R halt
put- - - R halt

back 0 0 L dup
back 1 1 L dup
back - - R halt
Initially        state = start        [-]001010
After move #1    state = start        -[0]01010
After move #2    state = start        -0[0]1010
After move #3    state = start        -00[1]010
After move #4    state = start        -001[0]10
After move #5    state = start        -0010[1]0
After move #6    state = start        -00101[0]
After move #7    state = start        -001010[ ]
After move #8    state = dup          -00101[0]
After move #9    state = put0         -001010[ ]
After move #10   state = back         -00101[0]0
After move #11   state = dup          -0010[1]00
After move #12   state = put1         -00101[0]0
After move #13   state = back         -0010[1]10
After move #14   state = dup          -001[0]110
After move #15   state = put0         -0010[1]10
After move #16   state = back         -001[0]010
After move #17   state = dup          -00[1]0010
After move #18   state = put1         -001[0]010
After move #19   state = back         -00[1]1010
After move #20   state = dup          -0[0]11010
After move #21   state = put0         -00[1]1010
After move #22   state = back         -0[0]01010
After move #23   state = dup          -[0]001010
After move #24   state = put0         -0[0]01010
After move #25   state = back         -[0]001010
After move #26   state = dup          [-]0001010
After move #27   state = put-         -[0]001010
After move #28   state = halt         --[0]01010

Where:

Also, the following are not part of the TM definition, but describe the states of this TM: