Hmmm... that??™s too bad... it would be nice to have a program to check our work and tell us whether or not
our new program will ever crash.
The mathematical conception of Turing??™s model of computation is called a Turing machine or TM. A TM
is usually described as a machine reading a tape.
?—? The tape contains symbols or blanks, and the tape can be infinitely long.
?—? The machine can read one symbol at a time, the symbol positioned under the ???read/write head??? of the TM.
?—? The machine can also erase the symbol, or write a new symbol, and it can then position the tape one
cell to the left or right.
?—? The machine itself can be in one of a finite number of states, and reading a symbol can cause the state
of the TM to change.
?—? A special state is the halting state, which is the state of the machine when it terminates normally.
CHAP. 2] ALGORITHMS 25
?—? When the machine starts, it is in state 1, it is positioned at the extreme left end of the tape, and the tape
extends indefinitely to the right.
A particular TM will have a set of instructions it understands. Each instruction consists of a 5-tuple (rhymes
with couple), which is a mathematical way of saying that one instruction consists of five values.
Pages:
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