[FOM] hypercomputation, Kieu, and Calude

[Toby Ord]

On 10 Mar 2004, at 23:33, Martin Davis wrote:

> 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.

It may be worth distinguishing between the study of mathematical models 
of 'computation' that compute more than Turing machines for 
mathematical or philosophical reasons (such as Hamkins' studies of 
infinite time Turing machines) and the study of how such computation 
might be physically possible. The former would seem to be on no shakier 
ground than recursion theory (and could be considered a part of it, 
depending on your inclination), while the second looks at the nature of 
the physical world. Regarding this second type of investigation, it is 
certainly important whether physical hypercomputation is possible and 
also an open question, so one should only regard such work as dubious 
if you think the approach taken within the analysis of this question is 
dubious.

If you think there are astounding reasons to believe there to be no 
physical possibility of hypercomputation, then this could be grounds to 
argue that the work of those trying to find such a possibility is not 
going to bear fruit, but I can see little reason to take one side over 
the other in this matter and think that both angles deserve equal merit 
until it is demonstrated otherwise. I can see no reasons (including 
that of majority of considered opinion) that weigh more heavily against 
a hypercomputational universe than that weighed against a non-euclidean 
universe before the days of general relativity.

(I should note that I don't think the fact -- if it is one -- that we 
could not tell if a proposed hypercomputer computed a given 
non-recursive function, counts against the possibility that such 
machines could exist, but it is certainly a topic of considerable 
interest regardless.)

> 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.

It seems to me that your above claim that Hilbert's 10th problem is 
'known to be unsolvable' is simply false. Of course it has been proven 
(and in part by you) that Hilbert's 10th problem is unsolvable by 
Turing machines or that it is recursively unsolvable, but not that it 
is unsolvable *simpliciter*, nor that we will never be able to make a 
physical machine that will reliably solve it. While I am unsure of 
exactly what you mean by 'unsolvable' without any qualifier, it would 
seem undeniable that it is an open possibility (although you might say 
an incredibly slight one) that we will one day have a machine that 
reliably solves it and that given this, for claim that it is 'known to 
be unsolvable' to be true, it would have to possess a very bizarre 
meaning indeed. On the other hand, if you just mean recursively 
unsolvable then that is clearly true, but not very relevant as your 
opponents agree with this.

When words like 'unsolvable' or 'uncomputable' get used as synonyms for 
'recursively unsolvable' or 'recursively uncomputable' (regardless of 
whether this is in fact occurring in your above paragraph) it can lead 
to dangerously persuasive arguments. For example, it might lead us to 
think that since Hilbert's 10th problem is 'unsolvable', we will never 
be able to make a machine to solve it. However, in this case, there is 
a slide from recursively unsolvable to unsolvable simpliciter which is 
making the argument invalid despite its surface appearance of validity.

It is this use of the abbreviated term 'computable' that I expressed my 
concern about in a previous posting, although it was rightly pointed 
out that the practice of doing so dates back to Turing himself. Still, 
I think that in philosophical conversations regarding at least two very 
distinct notions of computability of solvability, we need to be very 
clear not to use the same term for each.

> 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.

I look forward to reading this.

> In addition there will be subsequent postings on this matter.

And to these,

Toby Ord.