599 Lucas Hall (MC 73)
Email:
piccininig@umsl.edu
Abstract: This paper calls for more action on how to
properly understand and evaluate the Church-Turing thesis (CT). Following an established recent trend, I
distinguish between what I call
Discussion of Church’s thesis has
suffered for lack of a precise general framework within which it could be
conducted (Montague 1962, p. 121).
The Church-Turing thesis (CT) may be stated as follows:
CT: Any function that is intuitively computable
is computable by some Turing machine.
Or in Alan Turing’s terms, CT pertains to functions that may
be “naturally regarded as computable” (Turing 1936-7, p. 135).[2] This formulation should be
uncontroversial. Unfortunately, people
disagree on what is “intuitive” or “natural”.
As soon as we try to be more precise about the intuitive sense in which
functions are computable, agreement ends.
Since 1962, when Richard Montague urged us to be more rigorous in
discussing CT, the relevant literature has mushroomed. But no consensus has emerged on how to
discuss CT productively. Many pertinent
issues remain unclear. This paper calls
for more action on how to properly understand and evaluate CT and offers some tentative
suggestions on how progress might be made.
Following an established recent
trend, I distinguish between what I call
The correct physical analogue of
1. The Logical Church-Turing
Thesis
Many people suppose that the intuitive sense of “computable”
has to do with what can be done, or at least computed,[3] by
physical systems. This is too simplistic. CT was originally proposed and evaluated by
logicians. They were not investigating
the general properties of physical systems, but the foundations of
mathematics. They were concerned with
what can be learned by following certain procedures, namely, effective
procedures for generating values of functions defined over effectively denumerable
domains, such as the natural numbers or strings of letters over a finite
alphabet.
An effective
procedure in this sense may be informally characterized as follows:
•
The
procedure consists of a finite number of deterministic instructions
(i.e., instructions determining a unique next step in the procedure), which command
the execution of a finite number of primitive operations for a finite
number of times.
•
Instructions
are given by non-ambiguous specifications of finite length.
•
The
procedure requires no intuitions about the domain (e.g., intuitions
about numbers), no ingenuity, no invention, and no guesses.
•
For
each argument of a function the procedure is the same (uniformity).
•
If
the procedure generates the correct value of the function for each
argument (when the procedure terminates).
To determine what can be accomplished by following effective
procedures, different authors proposed and studied different formalisms, such
as Turing machines, general recursive functions, and λ-definable
functions. They suggested that these
formalisms capture in a precise way the informal notion of calculability by
effective procedure. Since
The logicians who initially proposed and endorsed CT
did not defend it based on the general properties of physical systems. Their main reasons were the following (Kleene
1952, § 62, § 67):
1) Argument from lack of counterexamples. Every function known to be effectively
calculable, and every operation for defining a function effectively from other
functions, has been shown to be computable by Turing machines (Turing-computable
for short).
2) Argument from failure of
diagonalization. Diagonalization over Turing
machines, which might be expected to yield a function that is not Turing-computable,
does not lead outside the class of Turing-computable functions.
3) Argument from confluence. A number of authors, working with different
primitive notions, defined different mathematical formalisms and proposed that
the functions definable within their formalism be identified as the class of
effectively calculable functions. Some
of the best-known formalisms are:
general recursiveness (Gödel
1934), l-definability (Church 1932, Kleene 1935), Turing-computability
(Turing 1936-7), and reckonability (Gödel 1936). These notions have been proven to be
extensionally equivalent to one another in the sense that any function that
falls within one of these formally defined classes falls within all of them. Since the different formalisms have little in
common and yet they all define the same class of functions, it is likely that
the class of functions so defined is the intended one.[5]
4) Turing’s argument. A Turing Machine seems capable of reproducing
any operation that a human being can perform while following an effective
procedure (Turing’s main argument for CT in his 1936-7 paper).
I will call these the original arguments for CT. It doesn’t take a detailed analysis to see
that the original arguments have little to do with the general properties of
physical systems. The view that CT
pertains to what can be done or computed by physical systems makes no sense of the
fact that most logicians accept CT on the grounds of the original arguments. Such view implies that logicians are confused
as to the proper justification for CT. Of
course, they might be confused in many ways, but it is implausible that they are
confused that badly. It is more
charitable to distinguish at least two versions of CT. One is the version that can be supported on
the grounds of the original arguments.
It may be called
During the
last two decades or so, the distinction between Logical and
There is
much to say about
Well, then, what shall we say about
what can be done, or computed, by physical systems in general?
2. The Bold Physical
Church-Turing Thesis
We need a physical version of CT that we can evaluate. This requires two things. First, we need to replace
The simplest starting point is the
following:
Bold
This is not very precise, but we need to start here because
in the literature,
(A) Any physical process can be simulated
by some TM (e.g., Deutsch 1985, Wolfram 1985, Pitowsky 2002).
(B) Any function over strings that is
computable by processes that manipulate arbitrary real numbers (in the sense
defined by Blum et al. 1998) is Turing-computable.
(C) Any system of equations describing a
physical system gives rise to solutions that are Grzegorczyk-computable (Earman
1986).
(D) For any physical system S and observable W, there is a Turing-computable function f: N ® N such that for all tÎN, f(t)=W(t) (Pitowsky 1990).
Many considerations are offered for
or against different formulations of
Each formulation of
2.1 Disparate Notions
The different formulations of
2.2 Falsification by Random Processes
Bold
More generally, formulations (A)-(D) would
be falsified by the existence of genuine random processes. According to the standard interpretation of
quantum mechanics, many fundamental physical processes, such as atom decay,
contain an objectively random element.
Hidden variable interpretations dispute this, but the possibility of
genuine randomness is sufficiently plausible that we should consider it. So, take a genuinely random process and count
its output at regular time intervals as constituting a string of digits.[9],[10] There are uncountably many infinite strings
of digits, but only countably many Turing-computable infinite strings. Therefore, assuming that all infinite strings
have the same probability of occurring as a result of a random process, the
probability that a random process would generate a Turing-computable string of
digits is zero. Thus, if we could use a
random process to generate a string, there is a sense in which we would have
physical means that go beyond what is Turing-computable. As Alan Turing pointed out, a machine with a
“random element” can do “more” than a Turing Machine (Turing 1950, pp.
438-439). It remains to be seen whether
this something “more” is relevant to
Someone might be tempted to bite the
bullet and conclude that if there are genuinely random processes, then
First, there is no way to define the
function f whose values are being
generated by P independently of running
P itself. Here, defining f means specifying the relationship between the arguments and
values of f, as we do when we define,
for instance, the halting function for Turing machines. (The halting function is the function that
returns ‘1’ if TM t halts on input x, ‘0’ otherwise.) If P
is genuinely random, there is no way to specify f without generating all values of f by running P. But normally, we are interested in
computation precisely because we are interested in learning the values of functions
defined independently of the processes that compute them. If we can’t find out what f is before we run P, we are not going to learn anything interesting by running P. Hence, we should not count P as physical computation, and we should
not count a thesis that is falsified by P’s
existence as a version of CT.
Determining which f is such that its values are generated
by a random process P is not only
impossible to do ahead of running P. It also contains an element of arbitrariness
that constitutes another disanalogy with genuine computation. For in the case of P, we can define indefinitely many f’s depending merely on which time intervals we consider when
observing P’s outputs. We could count P’s outputs per second, or millisecond, or year. Each temporal criterion will give rise to a
different f. By contrast, genuine computing mechanisms
come with a univocal criterion for what counts as the function being computed. For instance, in the case of Turing machines,
the function being computed is the one whose arguments and values are written on
the tape, respectively, at the beginning and at the end of the process.
A second reason against counting
random processes as computations is that they are not repeatable, whereas
computations must be repeatable.[11] Unrepeatable processes can only be observed
by the lucky few who happen to be in their presence. They cannot be used by others who might be
interested in learning from them. If no
one is present, no one can learn from an unrepeatable process. But again, computation matters to us (and to the
logicians who created computability theory) because we can learn from it. If we can’t repeat it when we need it, it is
not computation, and hence it is irrelevant to
Repeatability of a process is also helpful
to check that a process is performed correctly and hence that a computation is
reliable (see below). This may not
matter in the case of random processes, for there doesn’t seem to be any useful
sense in which a random process can perform incorrectly. If it can’t perform incorrectly, there is no
need to check for its correctness. But
this observation only reinforces the conclusion that random processes are not
computations, for random processes, unlike computations, cannot go wrong.[12]
A third reason is that P is not resettable. Ordinary computing mechanisms can be reset to
their initial state. Once they are back in
their initial state, they may be given the same input, which should
yield—barring malfunctions—the same computation. Thus, resettability plus repeatability of the
input entails repeatability of the process.
Resettability has other aspects too, independent of repeatability. One of the most interesting features of
computing mechanisms is that they can compute the same function for different
arguments, and those arguments can be chosen by the user. In the case of random processes, however, a “user”
has no way to choose which value of the function is generated. If she wishes to obtain the nth value of the function
whose values are generated by P, all she
can do is let P take its course and
wait until the nth value
is generated. If this won’t happen until
a million years from now, too bad for her.
Someone might object that the case of
a random process that takes too long to be useful is analogous to ordinary unfeasible
computation. But there is an important
disanalogy. The reason why ordinary
computations are unfeasible is that they take too many steps for our current
technology. Although some computations
require so many steps that they will always be unfeasible, that is beside the
point. For in general, as long as we shorten
each computational step, more and more (ordinary) computations become
feasible. Not so in the case of random
processes. There is no way to accelerate
a random process. If the function f whose values are produced by our
random process is defined to take one year per output digit, it will take one
thousand years to obtain the thousandth value of f. We can’t do anything to
speed it up. Again, this casts doubts on
the suggestion that a random process should be counted as relevant to
The above remarks converge on the
conclusion that a genuine random process, if there is such a thing, would not
count as genuine physical computation—relevant to Physical CT.[13] Any physical thesis that would be falsified
by genuine random processes is too strong to capture the notion of physical
computability—the notion that pertains to Physical CT.
2.3 Unconstrained Appeals to
Real-valued Quantities
Another feature that formulations (A)-(D) of
The expressive power of real numbers
may be used to generate a simple recipe to obtain the values of a Turing-uncomputable
function. Consider that the digital
expansion of a real number contains countably many digits. Hence, for any characteristic function (i.e.,
a function whose values are ‘0’ or ‘1’) defined over a countable domain,
including all Turing-uncomputable such functions, there is a real number whose
(binary) expansion encodes its values.
This is because for all values of such a function, the nth
value of the function may be defined to be the nth digit of
the (binary) expansion of a real number.
Suppose you wish to know the value of
a specific Turing-uncomputable function, such as the halting function for
Turing machines, for its nth argument. Take the real number r whose digital
expansion encodes the values of the halting function. All you need to do is obtain the value of the
nth digit in the binary expansion of r and you have the
result you desire. If you can do this,
you may obtain any value of any characteristic function defined over strings. This is a trivial result, and yet it is discussed
in the literature as an example of perhaps possible physical computation beyond
the power of TMs.[14]
Now, consider a different
observation. As I pointed out, many of
our physical theories assume that nature contains real-valued quantities that
vary along a continuum. These may
include the velocity of objects, the coordinates that define the position of
their center of gravity in the spacetime manifold, and more. If these physical theories are correct, then
many properties of many entities take arbitrary real numbers as their values. And most real numbers in any continuous
interval are Turing-uncomputable. In
fact, there are only countably many computable numbers, but any continuous
interval contains uncountably many real numbers. Thus, the probability that a randomly picked real-valued
quantity is computable is zero. Hence,
if our physical theories are correct, most transformations of the relevant
physical properties are transformations of Turing-uncomputable quantities into
one another. For instance, an object’s
change of speed, or even its simple change of spatial location are, in general,
transformations of one Turing-uncomputable real-valued quantity into
another. But a transformation of one
Turing-uncomputable value into another Turing-uncomputable value is certainly a
Turing-uncomputable operation. Hence, it
would seem that given many of our physical theories, the physical world is chock-full
of operations that outstrip the power of TMs.
Does this falsify
The problem lies in the unconstrained
appeal to operations defined over real numbers, or equivalently, real-valued
physical quantities, in formulating
In order to put the debate on more
fertile ground, we need to separate issues of physical computability proper
from other issues. Many questions about
the relationship between physical processes and computability deserve to be
asked. One question is, what are the
physically computable functions? This is
the question that should motivate
3. A Usability
Constraint on Physical Computation
These considerations suggest that appealing to what can be
done by physical systems without further constraints is not a legitimate
strategy for defining
Usability Constraint: Genuine physical computation may
be used by an observer to obtain the desired values of a function.[16]
The usability constraint can be articulated in terms of the
following sub-constraints, many of which respond to observations we made in
discussing the pitfalls of
1. Readable Inputs and Outputs. The inputs and outputs of a computation must
be readable. A quantity readable in this
sense is, at a minimum, one that can be measured exactly, so as to be used as
output, and either prepared or discovered by an observer, so as to be used as
input. One important reason why
computing technology is paradigmatically digital is that digital technology is
the only known way of manipulating inputs and outputs that are reliably readable.[17]
This constraint rules out arbitrary
real numbers. In order to measure a
real-valued quantity exactly at an arbitrary time, or even in order to measure the
exact value of an arbitrary digit in the expansion of a real-valued quantity,
an observer needs unbounded precision in measurement. Since the value of the variable may change
over time, the observer also needs unbounded precision in the timing of the measurement.[18] There is no reason to believe that such
unbounded precision is going to be available to us. Furthermore, there is no reason to believe
that we can discover the exact value of a real-valued quantity, either
computable or not, by means other than measurement. Finally, preparing a real-valued quantity
that encodes a Turing-uncomputable sequence, as is required by the simple
recipe discussed in Section 2.2, requires not only unbounded precision, but
also that we know the values of the Turing-uncomputable function that needs to
be encoded in the real number. This
requires that we already possess means to obtain those values, so as to compute
all values of the function. If we don’t,
our recipe—together with any recipe that requires the preparation of Turing-uncomputable
quantities—is useless. If we do, we
already have the means to obtain Turing-uncomputable sequences, and our recipe
is not adding any additional computing power.
Hence, the usability constraint rules out the unconstrained appeal to real-valued
quantities as inputs or outputs of computations.[19]
2. Process-Independent Rule. In a genuine computation, the problem being
solved (or equivalently, the function being computed) must be definable
independently of the process of solving it (computing it). A classic example of Turing-uncomputable
function is the halting function for Turing machines. The problem can be stated as a function from
strings of digits to strings of digits, without needing to appeal to arbitrary
real numbers. Hence, any putative
machine that solves the halting problem by reliably generating (measurable)
values of the function for any argument (of reasonable size) counts as a satisfying
the first sub-constraint (readable inputs and outputs). By contrast, as we saw above, a genuine
random process cannot be characterized as generating the values of an
independently specified function. That
is enough to rule it out of the class of genuine computations.
3. Repeatability. For something to count as a genuine
computational process, it must be repeatable by any observer at any time the
results are needed. Like the other
sub-constraints, repeatability must be taken with a grain of salt. It applies during ordinary conditions of use,
whatever they might be. It does not
entail that a computing mechanism must work under any physical condition, or
that computation must be instantaneous to allow for cases in which users want a
computation repeated immediately after it starts. Within ordinary conditions of use, it must be
possible to repeat a computation.
Repeatability is also needed to establish reliability (see below): One standard way to check that a computer is
not malfunctioning is to run the same computation more than once, making sure
that the results are the same every time.
(Of course, repeatability does not rule out all malfunctions, since the
results of repeated computations could be the same but still wrong.) Hence, if a process is not repeatable, it
does not count as computing.
4. Resettability. An ordinary computing mechanism is something
that, within its limits, can compute any value of one or more functions. Universal computers can compute any value of
any Turing-computable function, until they run out of memory or time. For this to be the case, it must be possible
for a user to reset the mechanism to its initial state and feed it different
arguments of the function being computed.
If this is not possible, and a user cannot choose which value of the
function is going to be generated by a mechanism, then that mechanism does not
count as computing.
5. Physical Constructability. If a mechanism cannot be physically
constructed, it may count as performing notional computations, but it is
irrelevant to
6. Reliability. To be useful, a computing mechanism must
operate correctly for a sufficient amount of time to yield correct
results. For this to happen, the
system’s components must not break too often, and the system’s design must be
such that noise and other external disturbances are generally insufficient to
affect the results. When large electronic
computers were initially proposed, some skeptics argued that their vacuum tubes
would break too often for the computers to be useful. The skeptics were proven wrong, but this was
no small feat. Even so, early electronic
computers broke often enough that they required full-time technicians devoted
to fixing them. Since then, computers have
become remarkably reliable; this contributes to making them useful and
accessible to a large public. The case of
early computers shows that even a relatively high degree of unreliability is
compatible with usefulness. But we
should be wary of computer designs that are guaranteed to break, or
self-destroy, or destroy the user (see below), before the results of the computation
can be known. Those early skeptics had a
point: if a machine is unreliable as a
matter of principle, it is not worth building.
This list of
constraints should be enough to illustrate the kind of property that is
required for something to be useful for physical computing, and hence to be
relevant to
4. The Modest Physical
Church-Turing Thesis
To formulate an interesting version of
A process may count as a physical
computation even if there is no effective procedure for describing the process,
perhaps because there are no finite instantaneous descriptions of the internal states
that constitute the process or no way to finitely and exactly specify the
transition from one instantaneous description to the next. Thus,
This proposal turns
What does it take for a
process to be relevant to
In summary,
Since
4.1 Support for Modest
The processes of ordinary digital computers, calculators, and
their components, including digital circuits, can be exhaustively described by
effective procedures. Thus, they are
already covered by
Connectionist
computing mechanisms have sometimes been proposed as computing mechanisms that
may go beyond Turing-computability.[22] But this conclusion is unwarranted. During the last two decades, there has been
considerable progress in the study of the computational and complexity
properties of large classes of connectionist computing mechanisms. The relevant systems have digital inputs and
outputs (so as to satisfy Constraint 1) but may have either digital or
non-digital internal processes. If we
restrict our attention to classes of connectionist systems that contain all
systems with current or foreseeable practical applications, the main results that
have been obtain are the following.
Feedforward networks with finitely many processing units are computationally
equivalent to Boolean circuits with finitely many gates. Recurrent networks with finitely many units
are equivalent to finite state automata.
Networks with unbounded tapes or with an unbounded number of units are
equivalent to Turing machines.[23]
In recent
years, two new approaches to computing have been developed. DNA computing exploits the combinatorial
power of thousands of molecules, and quantum computing exploits superposition
and entanglement. Although both DNA and
standard quantum computing promise to enhance the efficiency of certain
computations, neither approach goes beyond Turing-computability (Harel 2000).
So there are
good reasons to believe
In recent
years, several designs for hypercomputation have been proposed. Hypercomputation is computation of Turing-uncomputable
functions. If hypercomputation turns out
to be physically possible, it will refute
4.2 Challenges to Modest
To a first approximation, a hypercomputer is a system
that yields the values of a function that is not Turing-computable. If what counts as yielding the values of a
function is left unspecified, any of the systems discussed in Section 2, such as
genuinely random processes and processes that manipulate arbitrary real
numbers, might count as hypercomputational (provided they yield the values of
Turing-uncomputable functions). But in
discussing
The weakness of the sense in which counterexamples to
A genuine
hypercomputer is a physical system that satisfies at least the first four
constraints listed in Section 3:
readable inputs and outputs, process-independent rule, repeatability,
and resettability. If a system does not
satisfy one of these conditions, it does not even count as a computing. A system that does satisfy these conditions may
be purely notional. For instance,
infinitely accelerating TMs (Copeland 2002b) and infinitely shrinking computing
mechanisms (Davies 2001) satisfy these four conditions. These systems are purely notional, in the
sense that there is strong evidence that they can’t be built and used. Notional systems, of course, do not falsify
A spurious hypercomputer is a
physical system that fails to satisfy at least one of the first four
constraints. Examples include processes
defined over arbitrary real numbers (which violate Constraint 1) and genuine random
processes (which violate Constraints 2, 3, and 4). These putative hypercomputers are spurious
because they cannot be used and re-used by an observer to compute arbitrary
values of an independently defined function on an input chosen by the user, like
ordinary computing mechanisms can (given enough time and space). Since spurious hypercomputers are not
computing mechanisms, they are irrelevant to
Perhaps the best known proposal for a hypercomputer is
due to Mark Hogarth (1994), following an idea of Itamar Pitowsky (1990). I will now briefly discuss Hogarth’s proposal,
to further illustrate what is required for a genuine hypercomputer to falsify
Hogarth machines
exploit the properties of a special kind of spacetime, called Malament-Hogarth
spacetime, which is physically possible in the sense of constituting a solution
to Einstein’s field equations for General Relativity. Malament-Hogarth spacetimes contain what may
be called spacetime edges:
regions containing an infinite time-like trajectory l that can be circumvented by a finite
time-like trajectory g. In other words, l and g have a common origin, here called a bifurcation, and there
is a spacetime point p on g such that l lies entirely in p’s chronological past.
In addition to the operations performed by Turing Machines (TMs), Hogarth machines exploit five further primitive operations, described by the following instructions: (1) Position yourself at a bifurcation (where both l and g start); (2) Launch a TM along l while you remain on g; (3) Pass the edge (i.e., go to point p, by which time g has circumvented l); (4) Send a signal (from l to g); and (5) Receive a signal (coming from l).
With the resources offered by Hogarth
machines, we can define a procedure for solving the halting problem for Turing
machines. The halting problem asks,
given a TM t and an input x, does t halt on x? Exploiting the power of Hogarth machines, a
procedure for solving the halting problem can be defined as follows:
1. Prepare t with input x and add to
t’s instructions the instruction to
send a signal (from l to g) upon halting.
3. Launch t along l
while you remain on g.
4. Pass the edge while receiving a
signal if there is one coming from l.
In the finite time it takes an observer to travel through g, this procedure determines whether t halts on x. This is because by the
time g has circumvented l, which it will do by the definition
of Malament-Hogarth spacetime, the observer traveling through g will have received a signal if and
only if t halts on x.
Hence, the above procedure solves the halting problem for TMs.
Are Hogarth
machines genuine hypercomputers? They do
if they satisfy Constraints 1-4. Since
they operate on strings of digits, they satisfy Constraint 1 (readable inputs
and outputs). Since the function they
allegedly compute (e.g., the halting function) is defined independently of their
activity, they satisfy Constraint 2 (process-independent rule). As Hogarth initially defined them, however,
Hogarth machines fail to satisfy Constraints 3 (repeatability) and 4
(resettability). This is because in
Hogarth’s original definition, the Malament-Hogarth spacetime in which the
machine runs may contain only one spacetime edge. If there is only one edge, a Hogarth machine
may be run only once, on one input, in the history of the universe.
But Hogarth also defines
Malament-Hogarth spacetimes that contain an infinite number of edges. If those are available, we may assume that
each of them can be exploited to run a distinct computation. That gives us enough resources to repeat
computations or compute different values of the same function.[24] Although some components of a Hogarth machine
get lost in the course of the computation—they are never recovered after they
are launched along l—it
seems reasonable to assume that building a TM identical to the one previously
launched and launching it along a new infinite time-like trajectory counts as
resetting a Hogarth machine. Under these
assumptions, Hogarth machines satisfy Constraints 3 and 4.
Since they satisfy Constraints 1-4,
Hogarth machines are genuine hypercomputers.
It remains to be seen whether they falsify
Constructing a Hogarth machine is not
a trivial affair. The first question is
whether our spacetime is a Malament-Hogarth spacetime. The answer is currently unknown. If our spacetime is not a Malament-Hogarth spacetime, all bets are off. But even if it is, there remain considerable
obstacles. In order to exploit the
special properties of Malament-Hogarth spacetimes, Hogarth machines need to be
started at a bifurcation. So, for a user
to do anything with Hogarth machines, there must be bifurcations within regions
of spacetime that she can access. Otherwise,
if all bifurcations are out of reach, she cannot exploit them to run Hogarth
machines. Additionally, in order to
work with a Hogarth machine, a user needs to know that she is at a bifurcation.
She must also know how to launch a TM along the infinite trajectory l that starts at the bifurcation while
proceeding along the finite trajectory g. Finally, she must know when she has circumvented
l.
Hence, for Hogarth machines to be constructible, it must be possible to
discover when one is in the presence of a bifurcation, how to launch machines
along l’s, how to proceed along g’s, and when one has circumvented l’s.
An additional difficulty is that to
complete its computations, a Hogarth machine requires an actually infinite
memory.[25] In this, it differs from ordinary computing
mechanisms, which require an unbounded but always finite memory to complete
their computations. The reason for the
difference is that in order to compute the halting function, Hogarth machines
must be able to complete infinitely many computational steps, which may require
an infinite amount of memory. According
to Earman and Norton (1993), there might be spacetimes with enough space and
material to construct actually infinite memories. If this is correct, and if our other needs
are fulfilled—two big ifs—then Hogarth machines are physically constructible.
The final constraint is
reliability. It seems unlikely that a
machine with an infinite memory can operate for an infinite amount of time
without breaking down or running out of energy.
Even if this obstacle could be overcome, however, Earman and Norton have
pointed out a principled obstacle to the reliability of Hogarth machines. The signal traveling from l to g, which is needed for the user to know the result of the
computation, is subject to infinite amplification. If this is correct, then every time a signal
is received, the completion of the computation leads to the user’s destruction (Earman
and Norton 1993).
Hogarth machines are a fascinating
proposal. They are a fruitful
contribution to our discussion of computability and foundations of
physics. But it is unlikely that they will
ever satisfy our usability constraint.
If they don’t, then they don’t falsify
The same point applies to other designs
for genuine hypercomputers that have been proposed to date. These include infinitely accelerating TMs
(Copeland 2002b), infinite time TMs (Hamkins 2002), infinitely shrinking
computing mechanisms (Davies 2001), quantum computing mechanisms relying on
Hamiltonians with infinitely many energy levels (Kieu 2002), and computing
mechanisms with real-valued constants that encode infinite strings (Stannett
1990, Siegelmann 1999). All of these
proposals are genuine hypercomputers, but they won’t falsify
In the literature on physical computation, it is common to
encounter varying degrees of concern with whether existing proposals for
physical computation lead to physically usable processes (for a recent example,
see Ord 2006). But there are few if any
attempts to make explicit the constraints on what should count as a genuine
physical computation, or even better, a genuine physical computation that can
be used in practice. In this paper, I have
urged a more explicit and systematic treatment of this problem and the related
problem of formulating a reasonable version of
We should exert more care in
discussing
If we
formulate physical versions of
There is nothing wrong with changing
the subject, if one knows that one is doing so.
There are legitimate and interesting questions pertaining to what
aspects of what physical systems can be approximated to what degree, which
systems of equations give rise to solutions that are Grzegorczyk-uncomputable,
and more. These questions are not
directly related to CT, but they deserve to be investigated in their own right.
Physical CT should be formulated in a
modest way, using a notion of physical computation that is broader than that of
computation by effective procedure but considerably narrower than what can be “done”
by physical systems, in such a way as to satisfy a usability constraint on physical
computation: For a process to count as
genuine computation, it must be usable by a finite observer to solve certain
kinds of problem. I have offered such a
formulation in terms of reliable, constructible, repeatable, and resettable manipulation
of strings in accordance with fixed, process-independent rules (but without
appeal to effective procedures) and indicated why I think it may be useful in
discussions of CT.
Whether or not my formulation of
References
Black, R. (2000).
"Proving Church's Thesis." Philosophia Mathematica 8:
244-258.
Blum, L., F. Cucker,
et al. (1998). Complexity and Real Computation.
Church, A. (1932).
"A Set of Postulates for the Foundation of Logic." Annals of
Mathematics 33: 346-366.
Cleland, C. E. (1993).
"Is the Church-Turing Thesis True?" Minds and Machines 3:
283-312.
Churchland, P. M. and
P. S. Churchland (1990). "Could a Machine Think?" Scientific
American CCLXII: 26-31.
Copeland, B. J. (2000).
"Narrow Versus Wide Mechanism: Including a Re-Examination of Turing's
Views on the Mind-Machine Issue." The Journal of Philosophy XCVI(1):
5-32.
Copeland, B. J.
(2002a). "Hypercomputation." Minds and Machines 12:
461-502.
Copeland, B. J.
(2002b). "Accelerating Turing Machines." Minds and Machines 12:
281-301.
Copeland, B. J.
(2002c). The Church-Turing Thesis. The Stanford Encyclopedia of Philosophy
(Fall 2002 Edition). E. N. Zalta. URL =
<http://plato.stanford.edu/archives/fall2002/entries/church-turing/>.
Cotogno, P. (2003).
"Hypercomputation and the Physical Church-Turing Thesis." British
Journal for the Philosophy of Science 54: 181-223.
Davies, E. B. (2001).
"Building Infinite Machines." British Journal for the Philosophy
of Science 52(4): 671-682.
Deutsch, D. (1985).
"Quantum Theory, the Church-Turing Principle and the Universal Quantum
Computer." Proceedings of the Royal Society of
Earman, J. (1986). A
Primer on Determinism.
Earman, J. and J.
Norton (1993). "Forever is a Day: Supertasks in Pitowski and
Malament-Hogarth Spacetimes." Philosophy of Science 60:
22-42.
Folina, J. (1998).
"Church's Thesis: Prelude to a Proof." Philosophia Mathematica
6: 302-323.
Franklin, S. and M.
Garzon (1990). Neural Computability. Progress in Neural Networks. O.
Omidvar.
Gandy, R. (1980).
Church's Thesis and Principles for Mechanism. The Kleene Symposium. J.
Barwise, H. J. Keisler and K. Kuhnen.
Gandy, R. (1988). The
Confluence of Ideas in 1936. The Universal Machine: A Half-Century Survey.
R. Herken.
Gödel, K. (1934/1965).
On Undecidable Propositions of Formal Mathematical Systems. The Undecidable.
M. Davis.
Gödel, K. (1936).
"Über die Lange von Beweisen." Ergebnisse eines mathematischen
Kolloquiums 7: 23-24.
Gödel, K. (1946/2004).
Remarks Before the
Hagar, A. and A.
Korolev (2006). "Quantum Hypercomputability?" Minds and Machines
16: 87-93.
Hamkins, J. D. (2002).
"Infinite Time Turing Machines." Minds and Machines 12:
521-539.
Harel, D. (2000). Computers
Ltd: What They Really Can't Do.
Hartley, R. and H. Szu
(1987). A Comparison of the Computational Power of Neural Network Models.
Proceedings of the IEEE First International Conference on Neural Networks,
Hong, J. (1988).
"On Connectionist Models." Communications on Pure and Applied
Mathematics XLI: 1039-1050.
Hogarth, M. (1994).
"Non-Turing Computers and Non-Turing Computability." PSA 1994:
126-138.
Horgan 1997, cited by
Schonbein 2005.
Humphreys, P. (2004). Extending
Ourselves: Computational Science, Empiricism, and Scientific Method.
Kálmar, L. (1959). An
Argument Against the Plausibility of Church's Thesis. Constructivity in
Mathematics. A. Heyting.
Kieu, T. D. (2002).
"Quantum Hypercomputation." Minds and Machines 12:
541-561.
Kleene, S. C. (1935).
"A Theory of Positive Integers in Formal Logic." American Journal
of Mathematics 57: 153 - 173 and 219 - 244.
Kleene, S. C. (1952). Introduction
to Metamathematics.
Kleene, S. C. (1987).
"Reflections on Church's Thesis." Notre Dame Journal of Formal
Logic 28(4): 490-498.
Kleene, S. C. (1952). Introduction
to Metamathematics.
McCulloch, W. S. and
W. H. Pitts (1943). "A Logical Calculus of the Ideas Immanent in Nervous
Activity." Bulletin of Mathematical Biophysics 7: 115-133.
Mendelson, E. (1990).
"Second Thoughts about Church's Thesis and Mathematical Proofs." The
Journal of Philosophy 88: 225-233.
Minsky, M. (1967). Computation:
Finite and Infinite Machines.
Minsky, M. L. and S.
A. Papert (1988). Perceptrons: An Introduction to Computational Geometry.
Montague, R. (1962).
Towards a General Theory of Computability. Logic and Language: Studies
Dedicated to Professor Rudolf Carnap on the Occasion of His Seventieth Birthday.
B. H. Kazemier and D. Vuysje.
Mundici and W. Sieg
(1995). "Paper Machines." Philosophia Mathematica 3(3):
5-30.
Newell, A. (1980).
"Physical Symbol Systems." Cognitive Science 4:
135-183.
Odifreddi, P. (1989). Classical
Recursion Theory: The Theory of Functions and Sets of Natural Numbers.
Ord, T. (2006).
"The Many Forms of Hypercomputation." Applied Mathematics and
Computation 178: 143-153.
Ord, T. and T. D. Kieu
(2005). "The Diagonal Method and Hypercomputation." British
Journal for the Philosophy of Science 56: 147-156.
Piccinini, G. (2003).
"Alan Turing and the Mathematical Objection." Minds and Machines
13(1): 23-48.
Piccinini, G.
(forthcoming). "Computational Modeling vs. Computational Explanation: Is
Everything a Turing Machine, and Does It Matter to the Philosophy of
Mind?" Australasian Journal of Philosophy.
Piccinini, G.
(manuscript 1). "Computing Mechanisms.”
Piccinini, G.
(manuscript 2). "Computers.”
Pitowski,
Pitowski,
Pour-El, M. B. (1974).
"Abstract Computability and Its Relation to the General Purpose Analog
Computer (Some Connections Between Logic, Differential Equations and Analog
Computers)." Transactions of the American Mathematical Society 199:
1-28.
Schoenbein, W. (2005).
"Cognition and the Power of Continuous Dynamical Systems." Minds
and Machines 15(57-71).
Shagrir, O. (1997).
"Two Dogmas of Computationalism." Minds and Machines 7(3):
321-344.
Shagrir, O. (2002).
"Effective Computation by Humans and Machines." Minds and Machines
12: 221-240.
Shagrir, O. (2006).
Gödel on Turing on Computability. Church's Thesis after 70 years.
Heusenstamm, Ontos.
Shagrir, O. and
Shapiro, S. (1981).
"
Shapiro, S. (1993).
"
Sieg, W. (1994).
Mechanical Procedures and Mathematical Experience. Mathematics and Mind.
A. George.
Sieg, W. (1997).
"Step by Recursive Step: Church's Analysis of Effective
Calculability." Bulletin of Symbolic Logic 3(2): 154-180.
Sieg, W. (2002).
Calculations by Man and Machine: Conceptual Analysis. Reflections on the
Foundations of Mathematics (Essays in Honor of Solomon Feferman). W. Sieg,
R. Sommer and C. Talcott, Association for Symbolic Logic. 15: 390-409.
Sieg, W. (2005).
"Only Two Letters: The Correspondence between Herbrand and Gödel." Bulletin
of Symbolic Logic 11(2): 172-184.
Sieg, W.
(forthcoming). “Gödel on Computability.” Philosophia
Mathematica.
Siegelmann, H. T.
(1999). Neural Networks and Analog Computation: Beyond the Turing Limit.
Šíma, J. and P.
Orponen (2003). "General-purpose Computation with Neural Networks: A Survey
of Complexity Theoretic Results." Neural Computation 15:
2727-2778.
Siu, K.-Y., V.
Roychowdhury, et al. (1995). Discrete Neural Computation: a Theoretical
Foundation.
Smith, P.
(forthcoming). Gödel's Proofs.
Smolensky, P. (1988).
"On the Proper Treatment of Connectionism." Behavioral and Brain
Sciences 11: 1-23.
Soare, R. (1999). The
History and Concept of Computability. Handbook of Computability Theory.
E. R. Griffor.
Stannett, M. (1990).
"X-Machines and the Halting Problem: Building a Super-Turing
Machine." Formal Aspects of Computing 2: 331-341.
Turing, A. M. (1936-7
[1965]). On computable numbers, with an application to the
Entscheidungsproblem. The Undecidable. M. Davis. Ewlett, Raven: 116-154.
Turing, A. M. (1950).
"Computing Machinery and Intelligence." Mind 59:
433-460.
Welch, P. D. (2004).
"On the Possibility, or Otherwise, of Hypercomputation." British
Journal for the Philosophy of Science 55: 739-746.
Wolfram, S. (1985).
"Undecidability and Intractability in Theoretical Physics." Physical
Review Letters 54: 735-738.
van der Velde, F.
(1993). "Is the Brain an Effective Turing Machine of a Finite-state
Machine?" Psychological Research 55: 71-79.
[1] Thanks
to Darren Abramson, Jack Copeland, Martin Davis, John Earman, John Norton, Michael
Rabin, and Wilfried Sieg, among others, for helpful discussions on this
topic. Special thanks to Oron Shagrir
for correspondence and comments.
Material that led to this paper was presented at the 2005 Eastern APA
(meeting of the Society for Machines and Mentality) and to the Department of
Mathematics and Computer Science at the
[2] Turing talked about computable numbers rather than functions, but that makes no difference for present purposes.
[3] If every process is computational, there is no difference between what can be done and what can be computed. But as I argue elsewhere (Piccinini forthcoming), there are good reasons to distinguish computational processes from processes in general. For more on the difference between what can be done and what can be computed, see below.
[4] For more on the history of computability theory, see Davis 1982, Shapiro 1983, Gandy 1988, Sieg 1994, 1997, 2005, forthcoming, Soare 1999, Piccinini 2003, Shagrir 2006.
[5] The argument from confluence is the most popular in computer science, where CT is often formulated as the thesis that any new formalization of the notion of effectively calculable functions will yield the same old class—that of the Turing-computable functions (e.g., Newell 1980).
[6] E.g.,
Gandy 1980, Earman 1986, Odifreddi 1989, Pitowsky 1990, Mundici and Sieg 1995,
Sieg 2002, Shagrir 1997, Copeland 2002c, Shagrir and Pitowsky 2003. For examples of people who conflate or fail
to explicitly distinguish between Logical and
[7] On how to explicate Logical CT, see Kleene 1952, 1987, Gandy 1980, Shapiro 1981, 1993, Shagrir 2002, Sieg 2002, Copeland 2002c. On whether it’s provable, see Gandy 1980, Mendelson 1990, Shapiro 1993, Sieg 1994, 1997, Folina 1998, Black 2000, Smith forthcoming.
[8] Cf. Gödel’s remark:
Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing’s computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e., one not depending on the formalism chosen (Gödel 1946, p. 84, emphasis added).
[9] Later, I
will discuss a difficulty with doing this.
Since promoters of
[10] Terminological note: I use ‘digit’ to denote concrete counterparts of letters from a finite alphabet.
[11] I owe this observation to Michael Rabin. I don’t know if he would agree with the rationale I offer for it.
[12] For more on the possibility of miscomputation as a feature of genuine computation, see Piccinini ms 1.
[13] This is not to say that a random process cannot be useful for many purposes, including helping in certain computational techniques (cf. Copeland 2002a, pp. 480-481).
[14] Recipes along this line are discussed in the recent literature on hypercomputation. E.g., Copeland 2000.
[15] For more on computational approximation, see Humphreys 2004. For a more detailed discussion of (A) and its pitfalls, see Piccinini forthcoming.
[16] The usability constraint is an epistemic constraint, but it is weaker than the verifiability constraint discussed, and rightly rejected, by Shagrir and Pitowsky 2003, p. 90-1.
[17] This point is discussed in more detail in Piccinini ms 1, especially section 2.
[18] This creates a difficulty in counting the output of a genuine random process as a string of digits. For if an output occurs too close to the transition point between two digits, it may be practically impossible to establish whether it falls within a digit or its successor.
[19] Someone might ask, what about analog computers? Don’t they have real-valued quantities as inputs and outputs? Actually, analog computers (in the sense of Pour-el 1974) are designed to generate functions from real variables to real variables, which is not quite the same as functions from real-valued quantities to real-valued quantities. What they do is useful for solving certain classes of equations to a degree of approximation. It is not generally useful for computing in the sense relevant to CT. For more details on analog computers and their relation to digital computers, see Piccinini ms 2.
[20] Do all computations have to have inputs and outputs? The mathematical resources of computability theory can be used to define “computations” that lack either inputs, or outputs, or both. But the computations that are generally relevant for applications are computations with both inputs and outputs. Here I focus on the ordinary case.
[21] This condition rules out Kálmar’s “arbitrary correct methods,” which may change from one argument of a function to another (Kálmar 1959).
[22] Cf.: “connectionist models … may possibly even challenge the strong construal of Church’s Thesis as the claim that the class of well-defined computations is exhausted by those of Turing machines” (Smolensky 1988, p. 3). See also Horgan 1997, p. 25.
[23] For
some classical results and discussions, see McCulloch and Pitts 1943, Kleene
1956, Minsky 1967, Minsky and Papert 1988.
For more recent results, reviews, and discussions, see Hartley and Szu
1987, Hong 1988,
[24] Cf. Shagrir and Pitowsky’s discussion of their Objection #3, which they eventually handle in the same way (2003, p. 91-3).
[25] Cf. Shagrir and Pitowsky 2003, p. 90.
[26] For some related skepticism about some of these proposals, see Cotogno 2003. For a mistake in Cotogno’s paper (which is irrelevant here), see Welsch 2004 and Ord and Kieu 2005. For a critique of Kieu’s proposal, see Hagar and Korolev 2006. For a critique of Siegelmann’s proposal, see Schoenbein 2005.