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:

- 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
_{0}∈ 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.