[FOM] Re: The Myth of Hypercomputation

[Timothy Y. Chow]

On Mon, 9 Feb 2004, I wrote:
> 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)?

Upon further reflection, I think I have a partial answer to the concerns I
raised.  It seems to me now that the issue of extrapolating from finite
machines to Turing machines is actually a red herring.  I think that it
is the two following theses that are really at stake:

  Finite Verification Thesis:  Computations that admit a finite physical
  verification (i.e., finite observations of an experiment requiring
  a finite amount of resources [time, energy, error control, etc.] to
  prepare) confer an epistemological certainty that computations that
  don't admit a finite physical verification cannot.

  Finite Physical CT Thesis:  Computations that admit a finite physical
  verification coincide with the modern mathematical concept of a finite
  computation.

Another way to put it is that the real dividing line is not the
recursive/non-recursive dividing line, but the finite/infinite dividing
line.  Current work on hypercomputation is not really different from all
the well-known attempts to use classical physics to make "infinite
computations," except that the use of modern theories such as GR or
QFT gives it more superficial plausibility.  Since all these theories
use real numbers somewhere along the line (at least in their usual
developments), one can always find infinite (and non-recursive)
computations in the theory, but this is of no use unless one can
design a finite experiment to "extract" the computation.

Moreover, here's how I would respond to a "Kripkensteinian" skeptic (one
who gainsays the extrapolation from actual finite computers to Turing
machines).  I would *concede* that the computations of a finite computer
can be extrapolated to a non-recursive set and that there is no way to
test experimentally the claim that the "right" extrapolation is to a
recursive set.  The point is that, while the Church-Turing thesis and
recursion theory are useful theoretical tools, in practice the
computations we actually carry out today are finite computations anyway.
So if someone wants to make a different finite-to-infinite extrapolation
for theoretical purposes, we can let them be, as long as we agree on which
actual---and therefore presumably finite---computations to accept.

Advocates of hypercomputation, in my opinion, need to undermine either the
Finite Verification Thesis or the Finite Physical CT Thesis.  As I said,
it does no good merely to show that some physical theory or another admits
non-recursive phenomena.  One must *additionally* show that either

(1) some "infinite computation"---say, for concreteness, the consistency
of ZFC + "there exists a measurable cardinal"---admits a finite physical
verification (this would violate the Finite Physical CT Thesis), or

(2) we can have as much confidence in the output of an alleged
hypercomputer as we do in the output of ordinary computers, even
though the claim that the hypercomputer works correctly does not
admit a finite physical verification (this would violate the Finite
Verification Thesis).

Although both (1) and (2) seem unlikely, there is some wiggle room because
as I said before, it's not totally clear what "finite" means in physics.
But anyway, the point is that by focusing on the recursive/non-recursive
divide rather than on the finite/infinite divide, proponents of
hypercomputation have failed to direct attention to the real barriers to
acceptance of their ideas.

---------------------------------------------------------------------

On a different but related note, I wanted to respond to Dmytro
Taranovsky's question about the Standard Model by pointing out
the papers of Tien Kieu.

   http://arxiv.org/find/quant-ph/1/au:+Kieu_T

Naturally, the misgivings I've expressed above apply a fortiori to
Kieu's work, but you can judge his papers for yourselves.

---------------------------------------------------------------------

Also, I may have confused some readers by referring to Martin Davis's
paper---the contents of the paper have not been posted to FOM, but
as he's said, he is happy to email copies of it to anyone who is
interested.

Tim