[FOM] reply to Toby Ord re hypercomputation

[Martin Davis]

On March 10, 2004 Toby Ord wrote:

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

Naturally no reasonable person would quarrel with the study of mathematical 
models in the abstract. One would judge only on the basis of the 
mathematical interest and of the quality of the results that could be obtained.

Studying the question of the physical realizability in some sense of 
computations going beyond Church-Turing computability is certainly not 
beyond the pale. Way back in 1958, in my "Computability & Unsolvability" I 
wrote: "For how can we can we ever exclude the possibility of our being 
presented, some day 
with a 
device or “oracle” that “computes” a 
noncomputable function?" Certainly there *might* be some physical process 
currently unknown that could be harnessed to compute the noncomputable. But 
first it must be realized that there are conceptual problems in 
understanding what this even means because of the finiteness of ourselves 
and our observations. This is discussed in my papers mentioned before.

What is dubious is the hypercomputation movement that Jack Copeland has 
started to which he has contributed the name, some very questionable 
history regarding Church's Thesis and Turing's oracles, and the slogan "The 
search is on for some practicable way of implementing an oracle”.
I discuss this as well in my papers.

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

No one is arguing against the *possibility* that we may be living in what 
Toby Ord calls a "hypercomputational universe". My argument is two-fold. 
First that Turing's model of computation extends seamlessly to arbitrary 
devices built according to the laws of physics as we understand them today 
(see Church's review of Turing's paper quoted in my first paper and Robin 
Gandy's more extensive look at the matter). So it would take some really 
"astounding" development in our understanding of the physical world to go 
beyond this consensus, and thus the burden of proof lies heavily on the 
"hypercomputation" side. (An example of what such a development might be 
like is the idea - I don't have the reference at hand - that the 
relativistic properties of certain black holes are such that an infinite 
amount of time can occur in their vicinity and yet be observable by a 
finite being.) My second argument is that because we can not expect to 
observe more than finitely many outputs, assuring  ourselves that an 
alleged "hypercomputer" really is one, would be in the nature of things 
fraught with difficulty.


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

Of course not. But it certainly counts against its possible usefulness.

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

I was simply using the term "unsolvable" as it has come to be used in the 
literature, as the result of a widespread consensus. When I was young, I 
usually wrote "recursively unsolvable" (see my old book mentioned above) 
but that usage has come to seem somewhat quaint, since everyone (I'm sure 
including Toby Ord) knows what is meant. So I find his "simply false" 
(instead of a simple request that I use more exact terminology) a bit 
disingenuous. He certainly has my permission to mentally place the word 
"recursively" before "unsolvable" in anything I write.

Martin