FOM: physical computability

[JoeShipman@aol.com]

In a message dated 8/23/00 2:37:32 PM Eastern Daylight Time, 
mlerma at math.northwestern.edu writes:

<< That is not clear to me. For instance, a measurement process performed 
 on a quantum system usually yields random (hence non computable) results, 
 but that does not refute the Church-Turing thesis ("every algorithm can be 
 carried out by a Turing machine"), since the (non causal, non deterministic) 
 time evolution of a quantum system during a measurement process could
 hardly qualify as "algorithmic". I do not know what other people's intuition 
 for "algorithm" is, but I would not call "algorithmic" a process that 
 does not always yield the same result for identical inputs. >>


In the situation I described, the noncomputable sequence is not noncomputable 
because it is random, it is noncomputable because it is a mathematically 
definable but non-recursive sequence.  The randomness only enters the picture 
in making the probability that the output is the defined noncomputable 
sequence be some real number arbitrarily close to 1 rather than equal to 1.

The version of the Church-Turing thesis I am using here is different from 
yours.  You are rendering it as "every algorithm can be carried out by a 
Turing machine", while I am interested in the thesis "every function we can 
calculate by an effective procedure is calculable by a Turing machine".  The 
difference is that "algorithm" connotes some sort of mental step-by-step 
process, while "effective procedure" means ANYTHING we can do to obtain the 
sequence that works reliably.  Here "reliably" only need mean "with 
probability arbitrarily close to 1", not with certainty.   

Your version of the Church-Turing thesis is a weak one which just says that 
Turing machines capture the intuitive notion of algorithm.  It is a statement 
about PSYCHOLOGY.  My version is a stronger one which says that Turing 
machines can accomplish anything that can be accomplished by an "effective 
procedure".  It is a statement about PHYSICS.  A physical theory which 
entailed that a certain experimental procedure would produce a definable 
noncomputable bit sequence would refute my strong version of Church's thesis; 
I can't see how your weak version could be falsified.

-- Joe Shipman