MCIT

CIT 594 Turing Machine example
Spring 2012, David Matuszek

Here is the completion of the example we started in class. This example is a transducer: It shifts all the ones and zeros to the right, and fills in another minus at the left. That is, it transforms the string -A into the string --A, where A ∈ (0 ∪ 1)*, without violating Sipser's rule against moving left past the input data.

δ (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

δ (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:

Q is {start, dup, put1, put0, put-, back, halt}
- start -- move to the right end of the input
- dup -- find out what symbol to copy
- put1, put0, put- -- make a copy and move back to the original symbol
- back -- back up one more space
- halt -- stop
Γ is {0, 1, -, “blank”}
“blank” is " " on the tape, but # in the TM description
Σ is {0, 1, -}
q₀ ∈ Q is start
F ∈ Q (or q_accept ∈ Q) is halt; there is no q_reject, and
δ is the partial transition function given in the table above.

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

The TM starts on the leftmost input symbol.
The TM ends on the same symbol, shifted one to the right.