# FOM: physical computability

JoeShipman@aol.com JoeShipman at aol.com
Wed Aug 23 18:42:29 EDT 2000

```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

```