[FOM] reply to Toby Ord re hypercomputation
toby.ord at philosophy.oxford.ac.uk
Sun Mar 14 12:25:13 EST 2004
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
> 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.
More information about the FOM