Hypercomputation
Last Update: Friday, 5 April 2024 |
Note 1: Many of these items are online; links are given where they are known. Other items may also be online; an internet search should help you find them.
Note 2: In general, works are listed in chronological order.
(This makes it easier to follow the historical development of ideas.)
§11.1: Introduction
For a related, more general notion of computation, see
Piccinini 2020.
§11.4: Hypercomputation
Their form of computation
over the real numbers contains Turing computation as a special case.
§11.5: "Newer Physics" Hypercomputers:
For those of you curious about the epigraph to this section concerning
Malament-Hogarth hypercomputation, here are some suggestions:
His machines turn out to be related to Zeus
machines. The introduction is worth quoting:
And §2 ("The Story of Dave, HAL, and Goldbach") — a science fiction
tale to illustrate his argument — is very much worth reading!
§11.8.1: "Internal" vs. "External" Inputs:
§11.8.2: Batch vs. Online Processing:
§11.8.3: Peter Wegner: Interaction Is Not Turing-Computable:
On "isolation", see:
§11.8.4: Can Interaction Be Simulated by a Non-Interactive Turing Machine?
It is also sometimes called the "Parameter Theorem" or the "Iteration
Theorem"
(Davis and Weyuker 1983,
p. 64).
Rogers 1967,
Theorem IV, p. 22,
calls it the "enumeration theorem" (but distinguishes it from what
he calls the "s-m-n theorem"
(Rogers 1967,
Theorem V, pp. 23–24).
Rogers 1967,
p. 23, notes that it "shows that the computing
agent … need not be human" — because the human "computing agent"
in Turing's informal analysis can be replaced by a Universal Turing Machine.
In lectures at the University at Buffalo in the early 1980s,
Case used the mnemonic
"Stuff-em-in theorem" to emphasize that the external
inputs could be "stuffed into" the computer program.
Similar interpretations can be found in
Cooper 2004,
p. 64, and
Homer and Selman 2011,
p. 53.
Kfoury et al 1982,
p. 82, give a version of it stated in terms of computer programs.
§11.9: Oracle Computation:
§11.10: Trial-and-Error Computation:
Philosophers, logicians, and computer scientists have all contributed to
this theory:
§11.10.2: Does "Intelligence" Require Trial-and-Error
Machines?
and
Davis, M.D. (1993). How subtle is Gödel's theorem? More on Roger
Penrose. Behavioral and Brain Sciences, 16(3):611.
— that Gödel's Theorem can be viewed as a kind of hypercomputation.
§11.10.3: Inductive Inference:
For more information on "computational learning theory" and
"language learning in the limit", see:
"Any computer primed to perform an infinite number of computational
steps must take an eternity to complete the task, because
completion in a finite time would imply an unbounded signal
velocity — conflicting with relativity theory. This would seem to suggest
that the full potential of these computers is available only to immortal
computer users. But … there is no reason why the computer user must remain
beside the computer. If he follows a different worldline his clock
will tick at a rate different to that of the computer's clock, and perhaps
an extreme case could be organized in which the rates are such that the
finite proper time as measured by the computer user "corresponds"
to an infinite proper time as measured by the computer. In
this case, and granting also that the computer can always signal to
the computer user, the computer user will take only a finite time to
view the eternity of the computer's life and with it the results of its
computations." (pp. 173–174)
Copyright © 2023–2024 by
William J. Rapaport
(rapaport@buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/OR/A0fr11.html-20240405