195:. Since δ is built up from what we have assumed are Turing machines as well then it too must have a description number, call it e. So, we can feed the description number e to the UTM again, and by definition, δ(k) = U(e, k), so δ(e) = U(e, e). But since TEST(e) is 1, by our other definition, δ(e) = U(e, e) + 1, leading to a contradiction. Thus, TEST(e) cannot exist, and in this way we have settled the halting problem as undecidable.
186:, it is possible exhibit such an uncomputable function, for example, that the halting problem in particular is undecidable. First, let us denote by U(e, x) the action of the universal Turing machine given a description number e and input x, returning 0 if e is not the description number of a valid Turing machine. Now, supposing that there were some
74:, and transitions giving the current state, current symbol, and actions performed (which might be to overwrite the current tape symbol and move the tape head left or right, or maybe not move it at all), and the next state. Under the original universal machine described by Alan Turing, this machine would be encoded as input to it as follows:
190:
capable of settling the halting problem, i.e. a Turing machine TEST(e) which given the description number of some Turing machine would return 1 if the Turing machine halts on every input, or 0 if there are some inputs that would cause it to run forever. By combining the outputs of these machines, it
145:
But then, if we replaced each of the seven symbols 'A' by 1, 'C' by 2, 'D' by 3, 'L' by 4, 'R' by 5, 'N' by 6, and ';' by 7, we would have an encoding of the Turing machine as a natural number: this is the description number of that Turing machine under Turing's universal machine. The simple Turing
150:
may be interpreted as the code for at most one Turing machine, though many natural numbers may not be the code for any Turing machine (or to put it another way, they represent Turing machines that have no states). The fact that such a number always exists for any Turing machine is generally the
146:
machine described above would thus have the description number 313322531173113325317. There is an analogous process for every other type of universal Turing machine. It is usually not necessary to actually compute a description number in this way: the point is that every
101:
The UTM's input thus consists of the transitions separated by semicolons, so its input alphabet consists of the seven symbols, 'D', 'A', 'C', 'L', 'R', 'N', and ';'. For example, for a very simple Turing machine that alternates printing 0 and 1 on its tape forever:
96:
The transitions are encoded by giving the state, input symbol, symbol to write on the tape, direction to move (expressed by the letters 'L', 'R', or 'N', for left, right, or no movement), and the next state to enter, with states and symbols encoded as
241:
191:
should be possible to construct another machine δ(k) that returns U(k, k) + 1 if TEST(k) is 1 and 0 if TEST(k) is 0. From this definition δ is defined for every input and must naturally be
34:, every Turing machine can, given its encoding on that machine, be assigned a number. This is the machine's description number. These numbers play a key role in
167:. In the first place, the existence of this direct correspondence between natural numbers and Turing machines shows that the set of all Turing machines is
302:
250:
292:
277:
287:
183:
209:
31:
297:
282:
261:
192:
176:
83:
164:
246:
236:
159:
Description numbers play a key role in many undecidability proofs, such as the proof that the
172:
219:
160:
39:
204:
27:
214:
147:
23:
271:
232:
179:, there must certainly be many functions that cannot be computed by Turing machines.
30:, and are also occasionally called "Gödel numbers" in the literature. Given some
168:
35:
187:
82:
is encoded by the letter 'D' followed by the letter 'A' repeated i times (a
93:
is encoded by the letter 'D' followed by the letter 'C' repeated j times
42:, and are very useful in reasoning about Turing machines as well.
260:
Turing, A. M. "On computable numbers, with an application to the
120:, input symbol: blank, action: print 0, move right, next state: q
110:, input symbol: blank, action: print 1, move right, next state: q
242:
Introduction to
Automata Theory, Languages, and Computation
264:", Proc. Roy. Soc. London, 2(42), 1936, pp. 230–265.
16:
Numbers that arise in the theory of Turing machines
139:, the machine would be encoded by the UTM as:
8:
182:By making use of a technique similar to
22:are numbers that arise in the theory of
38:'s proof of the undecidability of the
62:, with a tape alphabet with symbols s
7:
155:Application to undecidability proofs
46:An example of a description number
14:
245:(1st ed.). Addison-Wesley.
1:
70:, with the blank denoted by s
303:Theoretical computer science
50:Say we had a Turing machine
26:. They are very similar to
171:, and since the set of all
319:
184:Cantor's diagonal argument
210:Universal Turing machine
32:universal Turing machine
142:DADDCCRDAA;DAADDCRDA;
127:Letting the blank be s
293:Models of computation
278:Theory of computation
257:(the Cinderella book)
288:Computability theory
262:Entscheidungsproblem
177:uncountably infinite
20:Description numbers
237:Jeffrey D. Ullman
173:partial functions
151:important thing.
89:The tape symbol s
310:
256:
318:
317:
313:
312:
311:
309:
308:
307:
268:
267:
253:
231:
228:
220:Halting problem
201:
193:total recursive
161:halting problem
157:
138:
134:
130:
123:
119:
113:
109:
92:
81:
73:
69:
65:
61:
57:
48:
40:halting problem
24:Turing machines
17:
12:
11:
5:
316:
314:
306:
305:
300:
298:Turing machine
295:
290:
285:
280:
270:
269:
266:
265:
258:
251:
227:
224:
223:
222:
217:
215:Church numeral
212:
207:
200:
197:
156:
153:
148:natural number
136:
132:
128:
125:
124:
121:
117:
114:
111:
107:
99:
98:
94:
90:
87:
79:
71:
67:
63:
59:
55:
47:
44:
15:
13:
10:
9:
6:
4:
3:
2:
315:
304:
301:
299:
296:
294:
291:
289:
286:
284:
281:
279:
276:
275:
273:
263:
259:
254:
252:0-201-44124-1
248:
244:
243:
238:
234:
233:John Hopcroft
230:
229:
225:
221:
218:
216:
213:
211:
208:
206:
203:
202:
198:
196:
194:
189:
185:
180:
178:
174:
170:
166:
162:
154:
152:
149:
143:
140:
115:
105:
104:
103:
95:
88:
85:
77:
76:
75:
54:with states q
53:
45:
43:
41:
37:
33:
29:
28:Gödel numbers
25:
21:
240:
205:Gödel number
181:
158:
144:
141:
135:and '1' be s
126:
100:
51:
49:
19:
18:
283:Alan Turing
169:denumerable
165:undecidable
78:The state q
36:Alan Turing
272:Categories
226:References
131:, '0' be s
188:algorithm
86:encoding)
239:(1979).
199:See also
116:State: q
106:State: q
66:, ... s
58:, ... q
249:
97:above.
84:unary
247:ISBN
235:and
175:is
163:is
274::
255:.
137:2
133:1
129:0
122:1
118:2
112:2
108:1
91:j
80:i
72:0
68:m
64:1
60:R
56:1
52:M
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.