[FOM] hypercomputation, Kieu, and Calude
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