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.

Turing Machine Grammar Comments
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#