Turing used the human as the model computing agent. He imagined a human, in a certain state of mind,
looking at a symbol on paper. The human reacts to the symbol on paper by
1 erasing the symbol, or erasing the symbol and writing a new symbol, or neither,
2 perhaps changing his or her state of mind as a result of contemplating the symbol, and then
3 contemplating another symbol on the paper, next to the first.
This model of computation captures the ability to accept input (from the paper), store information in
memory (also on the paper), take different actions depending on the input and the computing agent??™s ???state of
mind,??? and produce output (also on the paper). Turing recast this drastically simple model of computation into
mathematical form, and derived some very fundamental discoveries about the nature of computation. In particular,
Turing proved that some important problems cannot be solved with any algorithm. He proved not that these
problems have no known solution; he proved that these problems cannot ever have a solution. For instance, he
proved that one will never be able to write one program that will be able to determine whether any other arbitrary
program will execute to a proper completion, or crash.
Pages:
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