Since the machine can go no further in that direction, the machine ???crashes.???
Likewise, the TM will crash if one of the symbols on the tape is something other than 1 or 0. There are
no instructions in this TM for handling any other symbol, so an input tape such as this will also cause the TM to
crash:
0 3 0 ??† ??† original tape
Another way a TM can fail is by getting into an infinite loop. If instruction 7 above specified a move to the
left instead of the right, certain input tapes containing only 1s and 0s would cause the TM to enter an endless
loop, moving back and forth endlessly between two adjacent cells on the tape.
Algorithms can be specified as TMs and, like all algorithms, TMs must be tested for correctness, given
expected inputs.
CHAP. 2] ALGORITHMS 27
CHURCH??“TURING THESIS
The Turing machine is thought to be a very general model of computation. In 1936, logician Alonzo Church
advanced the thesis that any algorithmic procedure to manipulate symbols, conducted by humans or any
machine, can be conducted by some TM.
It is not possible to prove this proposition rigorously, for the notion of an algorithm is not specified mathematically.
However, the Church??“Turing thesis has been widely tested, and is now accepted as true.
Pages:
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