1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| # Add two numbers, according the the Boolos, et al., conventions.
# Erase a one and move to the right (state 0). If the first square is
# blank, move to the right and halt (state 1). Else, keep moving to
# the right until you find a blank (state 2). Write 1 there (state
# 2), move to the left until you find a blank (state 3). When you do,
# move back right (state 3) and erase a 1 and move right again (state
# 4). Halt.
# St R W M New
(0,1, ,1,r) # In state 0, if I see a 1,
# write a blank and move right and goto state 1.
# State 0: start state -- erase a one
(1, , ,99,r) # The first number was 0, so I'm okay.
(1,1,1,2,r)
# State 1:
(2, ,1,3,l) # Put a 1 in the first blank.
(2,1,1,2,r)
(3, , ,4,r) # Look for first blank
(3,1,1,3,l)
(4,1, ,99,r) # Erase first 1 and halt
(4, , ,1000,r) # Former halt state.
(3,1,1,1000,r) # Former halt state.
(2,1,1,1000,r) # Former halt state.
(99, , ,1000,r) # Former halt state.
(99,1,1,1000,r) # Former halt state.
(0, , ,1000,r) # Former halt state.
# Change 1111 to 4.
(100, ,0,200,r)
(100,1,1,140,r)
(101, ,*,104,l)
(102, ,1,103,r)
(103, , ,103,r)
(103,1, ,106,l)
(103,*, ,107,l)
(104, ,1,105,r)
(104,0,1,105,r)
(104,1,2,105,r)
(104,2,3,105,r)
(104,3,4,105,r)
(104,4,5,105,r)
(104,5,6,105,r)
(104,6,7,105,r)
(104,7,8,105,r)
(104,8,9,105,r)
(104,9,0,104,l)
(105,*,*,103,r)
(105,0,0,105,r)
(105,1,1,105,r)
(105,2,2,105,r)
(105,3,3,105,r)
(105,4,4,105,r)
(105,5,5,105,r)
(105,6,6,105,r)
(105,7,7,105,r)
(105,8,8,105,r)
(105,9,9,105,r)
(106, , ,106,l)
(106,*,*,104,l)
(107, , ,107,l)
(107,*, ,107,l)
(140,1,1,140,r) #Put an end of string marker
(140, ,*,141,l)
(141,1,1,141,l) #Goto lefthand 1
(141, , ,142,r)
(142,1, ,101,l)
(1000, , ,100,l) #Goto start state, machine u2d
(1000,1,1,100,l) #Goto start state, machine u2d |
