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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
The following is a low-level description of a Turing machine that will write
the Fibonacci sequence (represented in binary, separated by $) without halting.
A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where:
- Q is the set of states; non-empty and finite
- Σ is the input alphabet; non-empty and finite
- Γ is the tape alphabet; non-empty and finite
- δ is the transition function: δ(Q, Γ) -> (Q, Γ, {L, R})
- qI ∈ Q is the initial state
- qA ∈ Q is the accept state
- qR ∈ Q is the reject state
- Q: {
ca, cb, cc, cd, ce, cf, cg, ch, ci,
sa, sb, sc, sd,
aa, ab, ac,
aaa, aab, aac, aad, aae, aaf,
aba, abb, abc, abd, abe, abf,
ba, bb, bc,
baa, bab, bac, bad, bae, baf,
bba, bbb, bbc, bbd, bbe, bbf,
za, zb, zc, zd
}
- Σ: not relevant as we entirely disregard the input to begin with.
- Γ: {_, $, X, 0, 1, 0*, 1*} (_ means the blank symbol)
- δ: described below. a note on syntax:
- no entry in the output parameter means do not write a character to the tape.
- similarly, no entry in the position parameter means do not move the tape head.
- numerous "possible" transition functions are not stated. those are thought by the author to be inaccessible in normal operation of this machine (and if they are, it is probably a bug).
- qI: the initial state is ca.
- qA: the machine does not accept.
- qR: the machine does not reject.
Overview:
1. We clear the tape and write our initial state: the first three Fibonacci numbers
2. We write a number of Xs to the end of the tape for convenience
3. We add the last two numbers of the sequence digit-by-digit to create another number
- Effort/pain is taken to ensure carrying works: including when the next number is a digit larger
4. Upon having created the new Fibonacci number, we write a $ and repeat from step 3, ad nauseam
states c*: clearing the initial tape
- clear the tape: write $0$1$1$, then write _ until reading a _
δ(ca, Γ) -> (cb, $, R)
δ(cb, Γ) -> (cc, 0, R)
δ(cc, Γ) -> (cd, $, R)
δ(cd, Γ) -> (ce, 1*, R)
δ(ce, Γ) -> (cf, $, R)
δ(cf, Γ) -> (cg, 1, R)
δ(cg, Γ) -> (ch, $, R)
δ(ch, Γ \ _) -> (ci, _, R)
δ(ch, _) -> (sa, , )
states s*: making space for the next number
- from the end: append XX...X where len(XX...X) = len(previous_number)
δ(sa, {_,X}) -> (sa, , L)
δ(sa, $) -> (sb, , L)
δ(sb, {0*,1*}) -> (sb, , L)
δ(sb, 0) -> (sc, 0*, R)
δ(sb, 1) -> (sc, 1*, R)
δ(sb, $) -> (sd, , R)
δ(sc, Γ \ _) -> (sc, , R)
δ(sc, _) -> (sa, X, L)
δ(sd, {$,X}) -> (sd, , R)
δ(sd, 0*) -> (sd, 0, R)
δ(sd, 1*) -> (sd, 1, R)
δ(sd, _) -> (aa, , L)
states a*: add the last digit of both numbers without carrying
- read left until $, then read left until:
- 0: replace with 0*, goto state (aaa)
- 1: replace with 1*, goto state (aba)
- $: do not replace, read right until _, write $, goto state (s)
δ(aa, {X,0,1}) -> (aa, , L)
δ(aa, $) -> (ab, , L)
δ(ab, {0*,1*}) -> (ab, , L)
δ(ab, 0) -> (aaa, 0*, L)
δ(ab, 1) -> (aba, 1*, L)
δ(ab, $) -> (ac, , R)
δ(ac, Γ \ _) -> (ac, , R)
δ(ac, _) -> (sa, $, R)
states aa*
- read left until $, then read left until:
- 0*: replace with 0, read right until _, then read left until X and replace with 0
- 1*: replace with 1, read right until _, then read left until X and replace with 1
δ(aaa, {0,1}) -> (aaa, , L)
δ(aaa, $) -> (aab, , L)
δ(aab, 0*) -> (aac, 0, R)
δ(aac, Γ \ _) -> (aac, , R)
δ(aac, _) -> (aad, , L)
δ(aad, {0,1}) -> (aad, , L)
δ(aad, X) -> (aa, 0, L)
δ(aab, 1*) -> (aae, 1, R)
δ(aae, Γ \ _) -> (aae, , R)
δ(aae, _) -> (aaf, , L)
δ(aaf, {0,1}) -> (aaf, , L)
δ(aaf, X) -> (aa, 1, L)
δ(aab, {0,1}) -> (aab, , L)
states ab*
- read left until $, then read left until:
- 0*: replace with 0, read right until _, then read left until X and replace with 1
- $: do not replace, read right until _, then read left until X and replace with 1
- 1*: replace with 1, read right until _, then read left until X and replace with 0, goto state (b)
δ(aba, {0,1}) -> (aba, , L)
δ(aba, $) -> (abb, , L)
δ(abb, 0*) -> (abc, 0, R)
δ(abc, Γ \ _) -> (abc, , R)
δ(abc, _) -> (abd, , L)
δ(abd, {0,1}) -> (abd, , L)
δ(abd, X) -> (aa, 1, L)
δ(abb, 1*) -> (abe, 1, R)
δ(abe, Γ \ _) -> (abe, , R)
δ(abe, _) -> (abf, , L)
δ(abf, {0,1}) -> (abf, , L)
δ(abf, X) -> (ba, 0, L)
δ(abb, $) -> (abc, , R)
δ(abb, {0,1}) -> (abb, , L)
states b*: add the last digit of both numbers while carrying a one
- read left from end of tape, after reading $, until reading:
- 0: replace with 0*, goto state (baa)
- 1: replace with 1*, goto state (bba)
- $: do not replace, read right until _, goto state (za)
δ(ba, {X,0,1}) -> (ba, , L)
δ(ba, $) -> (bb, , L)
δ(bb, {0*,1*}) -> (bb, , L)
δ(bb, 0) -> (baa, 0*, L)
δ(bb, 1) -> (bba, 1*, L)
δ(bb, $) -> (bc, , R)
δ(bc, Γ \ _) -> (bc, , R)
δ(bc, _) -> (za, , L)
states ba*
- read left until $, then read left until:
- 0*: replace with 0, read right until _, then read left until X and replace with 1, then goto state (aa)
- 1*: replace with 1, read right until _, then read left until X and replace with 0, then goto state (ba)
δ(baa, {0,1}) -> (baa, , L)
δ(baa, $) -> (bab, , L)
δ(bab, 0*) -> (bac, 0, R)
δ(bac, Γ \ _) -> (bac, , R)
δ(bac, _) -> (bad, , L)
δ(bad, {0,1}) -> (bad, , L)
δ(bad, X) -> (aa, 1, L)
δ(bab, 1*) -> (bae, 1, R)
δ(bae, Γ \ _) -> (bae, , R)
δ(bae, _) -> (baf, , L)
δ(baf, {0,1}) -> (baf, , L)
δ(baf, X) -> (ba, 0, L)
δ(bab, {0,1}) -> (bab, , L)
states bb*
- read left until $, then read left until:
- 0*: replace with 0, read right until _, then read left until X and replace with 0, goto state (ba)
- 1*: replace with 1, read right until _, then read left until X and replace with 1, goto state (ba)
δ(bba, {0,1}) -> (bba, , L)
δ(bba, $) -> (bbb, , L)
δ(bbb, 0*) -> (bbc, 0, R)
δ(bbc, Γ \ _) -> (bbc, , R)
δ(bbc, _) -> (bbd, , L)
δ(bbd, {0,1}) -> (bbd, , L)
δ(bbd, X) -> (ba, 0, L)
δ(bbb, 1*) -> (bbe, 1, R)
δ(bbe, Γ \ _) -> (bbe, , R)
δ(bbe, _) -> (bbf, , L)
δ(bbf, {0,1}) -> (bbf, , L)
δ(bbf, X) -> (ba, 1, L)
δ(bbb, $) -> (bbc, , R)
δ(bbb, {0,1}) -> (bbb, , L)
states c*: scooting over the computed number to make space for a carried digit
- read left until $, then:
- read right, noting the current number and writing the previous number
- then go to state (sa)
δ(za, {0,1}) -> (za, , L)
δ(za, $) -> (zb, , R)
δ(zb, 0) -> (zc, 1, R)
δ(zb, 1) -> (zb, 1, R)
δ(zb, _) -> (zd, 1, R)
δ(zc, 0) -> (zc, 0, R)
δ(zc, 1) -> (zb, 0, R)
δ(zc, _) -> (zd, 0, R)
δ(zd, _) -> (sa, $, R)
|
