770
Modeling Arithmetic, Computation, and Languages
procedure or algorithm. In fact, if f is computed by the Turing machine T, then
the set of quintuples of T is itself the algorithm; as a list of instructions that can
be carried out mechanically, it satisfies the various properties in our notion of an
algorithm. Therefore, we are probably willing to accept the proposal illustrated by
Figure 9.19. The figure shows “computable by algorithm” as a “cloudy,” intuitive
idea and “Turing computable” as a mathematically precise, well-defined idea. The
arrow asserts that any Turing-computable function is computable by an algorithm.
Given the simplicity of the definition of a Turing machine, it is a little startling
to contemplate Figure 9.20, which asserts that any function computable by any
means we might consider to be an algorithm is also Turing computable. Combining Figures 9.19 and 9.20, we get the Church–Turing thesis (Figure 9.21), named
after Turing and another well-known mathematician, Alonzo Church.
Computable by
algorithm
Turing
computable
Computable by
algorithm
Turing
computable
Computable by
algorithm
Turing
computable
figure 9.19
figure 9.20
figure 9.21
tHeSiS ChurCh–turinG thEsis
A number-theoretic function is computable by an algorithm if and only if it is
Turing computable.
Because the Church–Turing thesis equates an intuitive idea with a mathematical idea, it can never be formally proved and must remain a thesis, not a theorem.
What, then, is its justification?
One piece of evidence is that whenever a procedure generally agreed to be
an algorithm has been proposed to compute a function, someone has been able to
design a Turing machine to compute that function. (Of course, there is always the
nagging thought that someday this might not happen.)
Another piece of evidence is that other mathematicians, several of them at
about the same time Turing developed the Turing machine, proposed other models
of a computational procedure. On the surface, each proposed model seemed quite
unrelated to any of the others. However, because all the models were formally
defined, just as Turing computability is, it was possible to determine on a formal,
mathematical basis whether any of them were equivalent. All the models, as well
as Turing computability, were proved equivalent; that is, they all defined the same
class of functions, which suggests that Turing computability embodies everyone’s
Modeling Arithmetic, Computation, and Languages
procedure or algorithm. In fact, if f is computed by the Turing machine T, then
the set of quintuples of T is itself the algorithm; as a list of instructions that can
be carried out mechanically, it satisfies the various properties in our notion of an
algorithm. Therefore, we are probably willing to accept the proposal illustrated by
Figure 9.19. The figure shows “computable by algorithm” as a “cloudy,” intuitive
idea and “Turing computable” as a mathematically precise, well-defined idea. The
arrow asserts that any Turing-computable function is computable by an algorithm.
Given the simplicity of the definition of a Turing machine, it is a little startling
to contemplate Figure 9.20, which asserts that any function computable by any
means we might consider to be an algorithm is also Turing computable. Combining Figures 9.19 and 9.20, we get the Church–Turing thesis (Figure 9.21), named
after Turing and another well-known mathematician, Alonzo Church.
Computable by
algorithm
Turing
computable
Computable by
algorithm
Turing
computable
Computable by
algorithm
Turing
computable
figure 9.19
figure 9.20
figure 9.21
tHeSiS ChurCh–turinG thEsis
A number-theoretic function is computable by an algorithm if and only if it is
Turing computable.
Because the Church–Turing thesis equates an intuitive idea with a mathematical idea, it can never be formally proved and must remain a thesis, not a theorem.
What, then, is its justification?
One piece of evidence is that whenever a procedure generally agreed to be
an algorithm has been proposed to compute a function, someone has been able to
design a Turing machine to compute that function. (Of course, there is always the
nagging thought that someday this might not happen.)
Another piece of evidence is that other mathematicians, several of them at
about the same time Turing developed the Turing machine, proposed other models
of a computational procedure. On the surface, each proposed model seemed quite
unrelated to any of the others. However, because all the models were formally
defined, just as Turing computability is, it was possible to determine on a formal,
mathematical basis whether any of them were equivalent. All the models, as well
as Turing computability, were proved equivalent; that is, they all defined the same
class of functions, which suggests that Turing computability embodies everyone’s