FOM: Church-Turing hypothesis -- reply to Vorobey and Davis

[Joe Shipman]

Vorobey writes:

> Suppose that you are facing a physical device that you suspect is the
> oracle for the halting problem.

> How, do you think, would you be able to *prove* that it really always
solves
> the halting problem correctly?


The same way you prove that an ordinary computer solves a recursively
solvable problem correctly -- in the context of a mathematized physical
theory.  You first need a physical theory in which mathematically
definable but nonrecursive funtions are experimentally accessible; if
the theory passes experimental tests and is acceptable *as physics*, one
can then derive as a consequence that a particular reproducible
experimental setup "computes" a nonrecursive function.

Since according to our current best theories certain experimentally
measurable quantities are equal to countably infinite sums of terms each
of which is a recursive real (with no proof that the sum exists or that
it is a recursive real if it does exist) this is not inconceivable.  (In
most cases the situation is more complicated, with the terms being
recursive in an experimentally measurable parameter such as the
fine-structure constant rather than purely recursive, but the parameter
may itself have a purely mathematical definition in the context of a
more complete theory in which case the argument goes through.)

This isn't a very good kind of nonrecursiveness because it depends an
measuring a number to arbitrary precision, though that is certainly
possible for some kinds of experimental quantities (for example the
ratio of the radioactive half-lives of two different kinds of atoms
where you can just count the decays in a very large sample -- you'd need
exponential time to get n bits of precision here).  But more feasible
kinds of nonrecursiveness aren't ruled out either.

The other way to "prove" that the physical device is an oracle for the
halting problem is just to observe that it always gives an answer, that
it never answers "no halt" for a machine that does halt, and that it
never answers "halt" for a machine that provably does not halt.  But for
this to be fully satisfactory you'd need some kind of explanation of how
the machine worked, which brings us back to the first answer.

By the way, earlier Davis drew a distinction between Church's_Thesis_1
(formalizing the informal notion of algorithm) and
C_T_2 (formalizing what is "computable" by real physical systems).  The
first is unfalsifiable while the second one has nontrivial scientific
content and could conceivably be shown to be false.  Since I have heard
the terms "Church's thesis" and "Church-Turing Hypothesis" but NOT
"Church's hypothesis" we seem to have a good linguistic solution:
*  "Church's Thesis" is Davis's C_T_1 (an assertion of equivalence
between an informal and a formal concept) which is unfalsifiable.
** The "Church-Turing Hypothesis" is Davis's C_T_2 (an assertion that
the laws of physics rule out a certain type of potentially
experimentally observable behavior, which is falsifiable).

The word "hypothesis" connotes something potentially disprovable much
more than the word "thesis" does.

-- Joe Shipman