FOM: physical computability

[Miguel A. Lerma]

JoeShipman wrote:
 > In a message dated 8/22/00 10:42:44 PM Eastern Daylight Time, 
 > shapiro+ at osu.edu writes: (MY COMMENTS INTERPOLATED IN CAPS -- J. SHIPMAN)
[...]
 > It seems that issues of determinism are wrapped in here. >>
 > NO, THIS WORKS IN A DETERMINISTIC OR A NONDETERMINISTIC PHYSICAL THEORY -- IN 
 > THE NONDETERMINISTIC THEORY YOU CAN ONLY OBTAIN THE NONRECURSIVE SEQUENCE 
 > WITH ARBITRARILY HIGH PROBABILITY RATHER THAN WITH CERTAINTY, BUT THAT STILL 
 > COUNTS AS A VIOLATION OF THE CHURCH-TURING THESIS.  

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.
(By the way, the research in quantum computing seems more concerned
with complexity issues than with computability, i.e., making
intractable problems tractable rather than computing uncomputable
functions.)

Concerning the distinction between computability and determinism, 
in his book "The Large, The Small and The Human Mind" Roger Penrose
describes a "toy model universe" whose time evolution is deterministic
but non computable.  The states of that universe consist of pairs of
finite sets of polyominoes of the form (S_q,S_r) - the (computable)
indexing function n -> S_n is assumed to have been fixed previously.
The initial estate of the universe is (S_0,S_0), and the rules of
(discrete) time evolution are as follows: from (S_q,S_r) the state of
the universe changes to (S_{q+1},S_r) if the set S_{q+1} tiles the
plane, otherwise it changes to (S_r,S_{q+1}). The evolution of this
universe is obviously deterministic, but since there is no computable
decision procedure to determine if a set of polyominoes tiles the
plane, that evolution cannot be computable.

Penrose's example seems more sophisticated than needed. In fact 
any well defined non computable function could be interpreted as
representing some deterministic non computable "process". But
Penrose's example has the virtue of resembling a natural phenomenon:
the fact that some states of physical systems are determined by global
properties of those systems. For instance, the only possible energy
levels of a particle in a box are the ones corresponding to
eigenstates represented by wave functions compatible with the boundary
conditions. Similarly, the evolution of Penrose's toy universe also
depends on global properties, namely the possibility of tiling the plane.
The natural laws in the real universe may also depend on non computable 
global solutions to well defined problems.


Miguel A. Lerma
Lecturer
Northwstern Univ Math Dept
Evaston, IL 60208