[FOM] On Hypercomputation

[Dmytro Taranovsky]

I think that given the current state of physics, it is too early to
judge whether hypercomputation is possible.  However, it is unlikely
that hypercomputers will be built in the near future, and I agree with
Martin Davis that one must watch out for naive designs for
hypercomputers.  Instead, scientists should investigate to what extent
hypercomputation is prohibited or permitted by their theories.  Although
neither general relativity (subject to certain limitations) nor
non-relativistic quantum mechanics (again subject to certain
limitations) features hypercomputation, newer theories appear to involve
infinity in a more essential way to arrive at finite results and, for
example, no one knows whether superstring theory involves
hypercomputation. 

One of the strongest arguments against hypercomputation is that, by
definition, a hypercomputer must accept input of arbitrary length--even
inputs much longer than two to the number of particles in the universe. 
Harvey Friedman introduces the notion of a weak hypercomputer, which is
capable of solving all instances shorter than a certain length of the
halting problem.  Weak hypercomputers are compatible with the physical
Church-Turing thesis, yet may have almost all of the practical benefits
of hypercomputation.  Also, one can verify if something is a weak
hypercomputer (see my posting "Experimentation, Incompleteness, and
Undecidability" on Feb 11, 2004), but to verify that a physical
procedure solves the halting problem, one must verify that the procedure
does not break down when the size of the input is larger than the number
of atoms in the universe--which is, as Martin Davis remarked, "fraught
with difficulty."


Dmytro Taranovsky