FOM: Various Church-Turing theses

[JoeShipman@aol.com]

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