[FOM] reply to Toby Ord re hypercomputation

[Toby Ord]

On 12 Mar 2004, at 00:04, Martin Davis wrote:

> 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 haven't seriously investigated Copeland's claims regarding Turing's 
conception of his o-machines, and indeed would not be all that 
interested in the truth of such claims anyway. Perhaps if they are 
intended to cite the support of the possibility of hypercomputation 
amongst those involved in the early days he would have done better to 
cite your 1958 comments, mentioned above.

Regarding the search being on for a practicable implementation, we 
should note that he said this in an article for Scientific American and 
was attempting to point out to the general readership that some people 
(indeed some who are not philosophers) are taking this seriously and 
investigating it. I guess the claim is technically true (given a loose 
enough reading of 'practicable'), but it does indeed suggest that more 
than a few dozen people are looking seriously at the problem and that 
there is hope for such a hypermachine in some kind of foreseeable 
future (such as the timeline that qubit quantum computation is looking 
at). In any event though, I am not bothered by these claims as their 
truth has no bearing on what I see as interesting and important in the 
(small) field.

> No one is arguing against the *possibility* that we may be living in 
> what Toby Ord calls a "hypercomputational universe".

Well, actually some people such as Paolo Cotogno in 'Hypercomputation 
and the Physical Church-Turing Thesis' (in Brit. J. Phil. Sci. 54 
(2003) 181-223.) do say just this, arguing that hypercomputation is 
incoherent for reasons that stem from the diagonal arguments. A reply 
to this particular paper by Tien Kieu and myself ('The Diagonal Method 
and Hypercomputation') is forthcoming in the same journal and available 
in preprint at http://arxiv.org/abs/math.LO/0307020

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

I have just written about this in some length in another reply, but in 
short, yes I do agree that depending on our physical findings the 
burden of proof can shift and we need not be exactly neutral about the 
matter. However, I think that at the moment it is quite fruitful to 
think about such things and explore which areas of QM or GR might admit 
hypercomputation, then see what a denial of physical hypercomputation 
would imply (such as precise claims regarding limits of measurement). 
In my view, this would be fertile investigation (indeed, regardless of 
whether or not hypercomputation is possible).

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

As I have said, I do agree that this is a serious issue (if not a fatal 
one). However, I don't think it is due to the finite number of outputs, 
but rather the inability to trace the computational paths 'by hand'. 
Otherwise the argument also applies to our belief that recursive 
computers are possible. I imagine you are not denying this, although 
one could do so.

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

I wasn't being disingenuous. There are arguments around to the 
conclusion that hypercomputation is a logical impossibility, and while 
I hold them to be fallacious, I was not sure whether this was what you 
meant. Perhaps I was swayed by your Lewis Carroll 'Impossibility' 
quotation and your comments that likened the search for 
hypercomputation to the search for a means of trisecting an angle with 
ruler and compass. While I do think there are useful analogies between 
study of physical hypercomputation and perptual motion machines, I 
don't see it in the comparison with trisection, whose impossibility 
within the self imposed constraints is deductively sound. However, 
thank you for clarifying your position.

Toby Ord.