CIT 594 Turing Machine to Unrestricted Grammar
Spring 2012, David Matuszek

I think the trouble I had in class was simply that I got mixed up about which direction I was going: TM to unrestricted grammar, or the reverse.

In any case, here's an example of a Turing Machine that adds 1 to a binary number. The Turing Machine starts with the read/write head on the leftmost digit and ends with the read/write head on the rightmost digit.

Input tape:` 101 ` `S → #s101# `

The initial production (only) of the grammar specifies the desired input string.

Abbreviations: `s=start`, `a=add1`, `f=finish`, `h=halt`.

```start 0 0 R start start 1 1 R start start # # L add1``` ```s0 → 0s s1 → 1s 0s# → a0# 1s# → a1# #s# → a## ``` As with MPCP, going right is a single production; going left requires a separate production for each tape symbol.
```add1 1 0 L add1 add1 0 1 R finish add1 # 1 R finish``` ```0a1 → a00 1a1 → a00 #a1 → a#0 a0 → 1f a# → 1f ``` For a move to the left,
`qx a b L qy`   becomes ` cqxa → qycb`
for every `c` in the tape alphabet.

For a move to the right,
`qx a b R qy`   becomes  ` qxa → bqy`
```finish 0 0 R finish finish 1 1 R finish finish # # L halt``` ```f0 → 0f f1 → 1f 0f# → h0# 1f# → h1# ``` By just following the rules, we should have the production
`#f# → h##`, but we don't really need that one.

Here's an example of using both the Turing Machine and the Unrestricted Grammar to add 1 to the binary number `101`:

Turing Machine example using 101 Transition to use Unrestricted Grammar example using 101 Production to use
`0 start  101` `start 1 1 R start` `S → #s101#` `s1 → 1s`
`1 start  101` `start 0 0 R start` `→ #1s01#` `s0 → 0s`
`2 start  101` `start 1 1 R start` `→ #10s1#` `s1 → 1s`
`3 start  101 ` `start # # L add1` `→ #101s#` `1s# → a1#`
`4 add1   101` `add1 1 0 L add1` `→ #10a1#` `0a1 → a00`
`5 add1   100` `add1 0 1 R finish` `→ #1a00#` `a0 → 1f`
`6 finish 110` `finish 0 0 R finish` `→ #11f0#` `f0 → 0f`
`7 finish 110 ` `finish # # L halt` `→ #110f#` `0f# → h0#`
`8 halt   110`   `→ #11h0# `