[FOM] reply to Toby Ord re hypercomputation
martin at eipye.com
Thu Mar 11 19:04:09 EST 2004
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
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.
More information about the FOM