[FOM] hypercomputation, Kieu, and Calude
Toby Ord
toby.ord at philosophy.oxford.ac.uk
Thu Mar 11 10:47:52 EST 2004
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.
More information about the FOM
mailing list