is called the Church-Turing Thesis. If we accept the CT-Thesis, we have to
conclude that "GlooP" is a myth-there are no restrictions to remove in
FlooP, no ways to increase its power by "unshackling" it, as we did BlooP.
This puts us in the uncomfortable position of asserting that people can
calculate Reddiag [N] for any value of N, but there is no way to program a
computer to do so. For, if it could be done at all, it could be done in
FlooP-and by construction, it can't be done in FlooP. This conclusion is so
peculiar that it should cause us to investigate very carefully the pillars on
which it rests. And one of them, you will recall, was our shaky assumption
that there is a decision procedure which can tell terminating from nonter-
minating FlooP programs. The idea of such a decision procedure already
seemed suspect, when we saw that its existence would allow all problems of
number theory to be solved in a uniform way. Now we have double the
reason for believing that any termination test is a myth-that there is no
way to put FlooP programs in a centrifuge and separate out the terminators
from the nonterminators.
Skeptics might maintain that this is nothing like a rigorous proof that
such a termination test doesn't exist. That is a valid objection; however, the
Turing approach demonstrates more rigorously that no computer pro-
gram can be written in a language of the FlooP class which can perform a
termination test on all FlooP programs.The Church-Turing ThesisLet us come back briefly to the Church-Turing Thesis. We will talk about
it-and variations on it-in considerable detail in Chapter XVII; for now it
will suffice to state it in a couple of versions, and postpone discussion of its
merits and meanings until then. Here, then, are three related ways to state
the CT -Thesis:
(1) What is human-computable is machine-computable.
(2) What is machine-computable is FlooP-computable.
(3) What is human-computable is FlooP-computable
(i.e., general or partial recursive).Terminology: General and Partial RecursiveWe have made a rather broad survey, in this Chapter, of some notions from
number theory and their relations to the theory of computable functions. It
is a very wide and flourishing field, an intriguing blend of computer science
and modern mathematics. We should not conclude this Chapter without
introducing the standard terminology for the notions we have been dealing
with.
As has already been mentioned, "Bloop-computable" is synonymous
with "primitive recursive". Now FlooP-computable functions can be di-
BlooP and F100P and GlooP^429