[FOM] hypercomputation, Kieu, and Calude

Martin Davis martin at eipye.com
Wed Mar 10 18:33:14 EST 2004

Jack Copeland's has maintained that Turing's notion of a Turing machine 
equipped with an oracle was intended to suggest that such an oracle might 
actually be built enable us to compute the uncomputable. Although this idea 
is simply ludicrous, Copeland, by inventing the term "hypercomputation", 
has provided an umbrella for all sorts of dubious work suggesting various 
ways in which this might be accomplished. There was even a special session 
of the American Mathematical Society devoted to some of this.

Tien Kieu has proposed to use quantum mechanics to provide a way to 
determine whether a given polynomial equation with integer coefficients has 
an integer root, thus solving Hilbert's 10th problem, known to be 
unsolvable. Cristian Calude and Boris Pavlov claim to have a probabilistic 
algorithm for solving the halting problem.

I have already mentioned my paper "The Myth of Hypercomputation" in which I 
discuss Copeland's ideas and related proposals by Hava Siegelman. I've 
written another "Computability, Computation, and the Real World" which also 
discusses the work of Kieu as well as Calude and Pavlov. Either or both are 
available as PDF attachments on request.

In addition there will be subsequent postings on this matter.


More information about the FOM mailing list