FOM: Various Church-Turing theses
JoeShipman@aol.com
JoeShipman at aol.com
Tue Jan 30 12:31:13 EST 2001
In a message dated 1/30/01 9:42:30 AM Eastern Standard Time,
V.Sazonov at doc.mmu.ac.uk writes:
<<Finally, let me ask, what is the difference between
CT and any other situation when mathematicians found
a formalization of an informal concept (like continuity
in terms of epsilon-delta or topological space) and
assert a deep satisfaction concerning the relation
between intuition and its formalization? What is so
special here about CT? I think - nothing, expect our
special interest to computability rather than, say,
to continuity notion. >>
For the version of the Church-Turing thesis "CT-psych" which asserts that any
intuitively computable function can be computed by a Turing machine, we are
talking about psychology and Professor Sazonov is essentially correct. For
the version of the Church-Turing thesis "CT-phys" which refers not to the
intuitive notion of computation but to effective procedures, we are talking
about physics and there is a philosophical significance to CT beyond the
assertion of satisfaction that an intuitive concept has been formalized.
In particular, if our best theories of physics lead us to conclude that a
certain reproducible experimental procedure will generate a sequence that is
mathematically definable but not computable, then CT-phys will be false, but
CT-psych may still be true because the relevant experimental procedure may
not have any relation to procedures humans can carry out with pencil and
paper. This kind of thing is already well-known in the field of Quantum
Computation -- while ordinary computers can be simulated by a human (armed
with unlimited pencils and paper) with only a linear slowdown factor, because
they operate by procedures similar to human pencil-and-paper calculation,
quantum computers can only be simulated by humans or Turing machines (so far
as we know) with an exponential slowdown factor because we must do
sequentially what they can do in parallel.
CT-phys is a strong assertion about what kinds of physical phenomena can
actually occur. The recent work in quantum computation suggests that the
stronger assertion CT-phys-P "any function that can be calculated by an
effective procedure can be calculated by a Turing machine with at most a
polynomial slowdown factor" is false. The current models of quantum
computation can in fact be simulated by TM's with an exponential slowdown,
but (given the incomplete state of our fundamental physical theories) there
is no reason at present to suppose that other quantum systems must also be
simulable by Turing machines.
To summarize: CT-phys may be false because the universe may support
reproducible experiments generating a mathematically definable but
nonrecursive sequence (the metamathematical importance of this doesn't depend
on being able to get infinitely many values of the sequence, since for any
definable but nonrecursive sequence F(n) there will be a particular m such
that ZFC does not determine the value of F(m)).
As far as CT-psych (intuitive computability) is concerned, I think the
identification of total recursive functions with intuitively computable
functions is more secure than the identification of partial recursive
functions with intuitively enumerable sets (or one-sided computable
functions). The prescription "simultaneously for all N search for proofs
that the Nth Turing machine computation does not halt, extending your
mathematical axioms beyond ZFC using appropriate mathematical methods, and
outputting those N where a proof is found", while vague, could provide a
counterexample.
-- Joe Shipman
More information about the FOM
mailing list