[FOM] Re: On Hypercomputation

[Dmytro Taranovsky]

On Sun, 2004-03-14 at 18:23, Timothy Y. Chow wrote:
> Dmytro Taranovsky <dmytro at mit.edu> wrote:
> > 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.
> 
> Surely this is not an argument against hypercomputation.  By definition, a
> Turing machine must also accept input of arbitrary length.  I don't think
> you intend to say that this is one of the strongest arguments against the
> Turing machine.

A strong argument can be made that it is not technologically possible
for a computer to have 2^(2^100) bits of RAM.  You are correct that the
argument, if successful, would also imply that Turing machines other
than finite automatons do not physically exist.

A number of designs for weak hypercomputers--including the rotating
black hole design by Etesi and Nemeti--require an ability to do an
unlimited amount computation (using an unlimited amount of RAM), and to
do so in finite proper time.  Such ability is certainly less plausible
than computers with 2^2^100 bits of RAM.  

Perhaps, however, the solution to every instance of the halting problem
shorter than a certain length can be  computed directly by a physical
process using a new primitive of computation.  Such a new primitive
(unlike, for example, the Nor gate) would have to accept input of large
length, so realizing it--even if it is predicted by the theory--is
likely to lead to problems similar to ones that currently plague quantum
computers.  (Quantum computation has only been successful up to 7 bits
because of the difficulty in maintaining many qubit quantum states.)

>I don't know what exactly you mean by the "physical Church-Turing
>thesis" ...   Your "weak hypercomputer" 
> could presumably solve this instance of the halting problem 
> and it is difficult to see in what sense this is "compatible  
> with the physical Church-Turing thesis" 

Physical Church-Turing thesis says that every physical process can be
modeled--and the correct probabilities for the outcomes of the process
obtained--by a Turing machine.  A weak hypercomputer is compatible with
physical Church-Turing thesis because its operation can be modeled by a
Turing machine.  To model a weak hypercomputer that accepts as input
codes for Turing machines consisting of less than n states, it suffices
to know a code for Turing machine that takes the longest number of steps
to halt on an empty tape among Turing machines that halt on an empty
tape and have less than n states.  However, to model such a weak
hypercomputer efficiently, a look up table of size exponential in n is
probably required.  Also, the ability to build weak hypercomputers for
arbitrary n would negate the physical Church-Turing thesis.

A statement related to the physical Church-Turing thesis is that there
will be no physical machines that take as input a code of Turing machine
with less than 2^20 states and output with high probability whether the
Turing machine halts on an empty tape.

>Let's put it this way: Suppose one builds
> an alleged "weak hypercomputer" that can tell us whether an ordinary 
> Turing machine that searches for an inconsistency in ZFC+MC (MC = 
> measurable cardinals exist) halts.  How exactly do you propose to
> verify that this alleged weak hypercomputer is really a weak hypercomputer 
> and correctly answers that question

Harvey Friedman's scenario of aliens with the crystal ball (along with
possible charges of an alien conspiracy) is not very realistic.  More
likely, a theory will make a large set of coherent predictions, which
will be confirmed by the experiment.  The predictions involve, in some
essential way, an analysis of infinite sets.  A recursive power series
approximating the predictions exists, but it often fails to converge.
	Eventually, under the scenario, a number of seemingly unrelated
predictions will be made by the theory in ZFC+PD but which imply
Con(ZFC) (in a weak base theory).  The predictions will be confirmed by
the experiment.  In addition, the theory together with experiment will
resolve in seemingly the right way many outstanding mathematical
questions, including the Riemann hypothesis. The results will form a
beautiful and coherent network, with most proofs human accessible.  In
cases where a contradiction is found, a proof of the contradiction can
usually be extracted, and in contrived cases--like ZFC + there is a
proof of contradiction in ZFC+PD involving not more than Ackermann
Function from (10, 10) steps--a proof that the system is contradictory
can be found (by further experimentation) in the weakest natural
appropriate system.  The results obtained using such a theory will be
accepted in the same way that the Four Color Theorem is generally
accepted as true even though no human has yet verified its proof.

As far as I know, it has not yet been ruled out that such a theory is
... the Standard Model.


Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm