From: pollack@dendrite.cis.ohio-state.edu (Jordan B Pollack)
Subject: Re: on Turing-Church hypothesis
Originator: pollack@dendrite.cis.ohio-state.edu
Reply-To: pollack@cis.ohio-state.edu
Organization: Ohio State Computer Science
Date: Wed, 8 Apr 1992 18:34:09 GMT

>It follows that most chaotic processes cannot be simulated by 
>a Turing machine.

Then why do most people working on dynamical systems simulate them
with computer programs? There are interesting relationships between
dynamical systems and computation, but it is not so trivial as
the discrete/continous distinction.

>ASSUMING THAT SPACE AND TIME ARE CONTINUOUS, then, due to its
>finiteness, a Turing machine cannot exactly represent an arbitrary
>dynamical system. 

Time and space are merely TREATED AS CONTINOUS to make the mathematics
work smoothly. Rather than making assumptions, you could ask whether
the physical universe is capable of performing actions or DIRECTLY
representing mathematical concepts which are not computable. For
example, if an ideal circle could be built out of matter, then you
would be right, because we cannot DIRECTLY and fully represent PI in a
physical machine. Unfortunately all PHYSICAL circles are (merely
computable) approximations, for if you keep measuring the diameter and
radius on a finer and finer scale, eventually their ratio will diverge
from PI.  Can you prove time is continuous? Try to build equipment to
measure smaller and smaller ticks of a clock: eventually your
equipment will need circuitry faster than the speed of light.

Just as doubling an initial angle in the unit circle will eventually
be deterministically random (because one is asking for more and more
bits from PI), so the universe itself cannot represent initial
conditions to the irrational accuracy required for predictability.
This reason for chaotic sensitivity in nature supports rather than
attacks the thesis of the "universal" equivalence of computation
systems: it is because the universe cannot implement its own unbounded
and continous mathematical ideals that unpredictability keeps getting
introduced.  

There are dynamical systems folk trying to find the "real" computation
within their framework. See:

%A S. Wolfram
%T Universality and Complexity in Cellular Automata
%J Physica
%V 10D
%P 1-35
%D 1984


%A C. Moore
%T Unpredictability and undecidability in dynamical systems
%J Physical Review Letters
%V 62
%N 20
%P 2354-2357
%D 1990

%A J. P Crutchfield
%A K. Young
%T Computation at the Onset of Chaos
%B Complexity, Entropy and the Physics of INformation
%E W. Zurek
%C Reading, MA
%I Addison-Wesley
%D 1989

%A C. G. Langton
%T Computation at the Edge of Chaos: phase transitions and
emergent comptutation
%J Physica D
%V 42
%D 1990
%P 12-37

and, of course

%A J. B. Pollack
%T The Induction of Dynamical Recognizers
%J Machine Learning
%V 7
%P 227-252
%D 1991

-- 
Jordan Pollack                            Assistant Professor
CIS Dept/OSU                              Laboratory for AI Research
2036 Neil Ave                             Email: pollack@cis.ohio-state.edu
Columbus, OH 43210                        Phone: (614)292-4890 (then * to fax)
Xref: sparky comp.ai.philosophy:4302 sci.lang:4066