[FOM] The Myth of Hypercomputation

[Timothy Y. Chow]

Martin Davis's excellent article, "The Myth of Hypercomputation," clearly
articulates several criticisms of the hypercomputation movement that I
have had floating around vaguely in my head for the past couple of years.
There is one nagging point that still bothers me, which I will try to
explicate now.

The first thing I want to say is that I think the concept of "finite" as
applied to the physical world is subtler than it seems at first.  Even
for a task as simple as counting the number of marbles in a jar, my
assignment of a positive integer to that quantity is predicated on some
important physical assumptions.  For example, I presuppose that I am able
to control the environment to the point where I can ensure that no marbles
enter or leave the jar, and that if I exert such control and repeat the
count, I will get the same number.  This might sound trivial, but if you
have ever had a dream where you keep doing some calculation and it comes
out different every time, you will see that there is a substantial
assumption entering here.

For measurements other than counting, "finite" is even slipperier.  On
the surface at least, the world (including our bodies and our measuring
instruments) appears to be analogue, and it is only in our minds that
we convert certain analogue stimuli into finite-precision digital records.

Suppose, however, we somehow solve the problem of making precise the notion
of a "finite physical measurement."  One argument against hypercomputation
is that even if someone hands me a hypercomputer (that solves the halting
problem, say), I cannot verify that it really works as advertised from a
finite set of finite measurements.  Without the ability to make a finite
verification, I can never really "know" that the hypercomputer is "really
solving" the halting problem.  Davis quotes Dana Scott as making essentially
this argument.  While I like this argument, what worries me is that
the same argument appears to prove that I can never "know" that an
ordinary computer is "really computing" (say) the product of two numbers.
That is, I can check that the ordinary computer is correctly implementing
a particular finite-state automaton (since we're assuming we know what a
"finite set of finite measurements" is), but I can't rule out pathological
("Kripkensteinian"?) extrapolations that say that the ordinary computer is
actually a truncated hypercomputer rather than a truncated Turing machine.

So here's what I am wondering: Is it possible to make precise exactly
what kinds of extrapolations we allow ourselves to make in physics, to
the point that one could *prove* that a hypercomputer---or more precisely,
the belief that a certain physical machine is a hypercomputer---is
impossible unless certain fundamental beliefs about how we human beings
interact with the physical world are overturned (and at the same time
blocking a similar "proof" that it is impossible to believe that ordinary
computers approximate Turing machines)?

Another way to put it, perhaps less precise but more suggestive, is that
I think the right question is not the "objective" question of whether
a machine that computes uncomputable functions can be physically built, but
the "subjective" question of whether we could ever *come to believe* that
a particular machine is in fact a hypercomputer.  Most of what I have read
on the "physical Church thesis" focuses on the objective question while
giving short shrift to the subjective question.

Finally, let me reproduce a thought experiment that I posted on sci.logic
last year.  It illustrates some of the above issues.

Suppose that you encounter a machine that allegedly solves the halting
problem.  You ask the computer, "Would a machine that blindly searches for
a proof of a contradiction from the axioms `ZFC + [some humongous
cardinal] exists' halt?"  The computer prints out, "No."  How should you
interpret this incident?

a) The computer's answer increases your confidence in the consistency of
   "ZFC + humongous cardinal" by directly computing the answer for you.

b) The incident is an experimental test of the physical theory that
   led to the prediction that the computer is indeed a "hypercomputer,"
   and your a priori confidence in the consistency of "ZFC + humongous
   cardinal" increases your confidence in the correctness of the physical
   theory.

c) Neither a nor b; you have gained no information about large cardinals
   or about the possibility of hypercomputation.

Tim