FOM: Precision and Turing-computability

[José Félix Costa]

Dear Paul:

Dynamical systems with real-valued parameters can compute non-computable
functions. In particular neural nets with real weights.

Discrete time:
Low dimension dynamical systems -- see Cris Moore, Pascal Koiran, ...
High dimension dynamical systems -- see Hava Siegelmann and Eduardo Sontag,
Max Garzon, ...
Church-Turing does not apply

Continuous time:
Diferential equations -- see Brannicki, Pekka Orponen, ...

Real parameters are the limit of the classical physical reality. In quantum
reality, physical magnitude can not be mesured with infinite precision.
Moreover the amount of energy needed to compute above Turing is infinite.
However even if we can't mesure with infinite precision, this does not mean
that we can't imagine physical models, working with real-valued parameters.

''For any given finite precision, any physical phenomenon can be predicted
by a Turing machine with this precision''.

In fact this is not true, since if we embed Turing machines in any physical
phenomenon, then we lift to the physical realm the indecidability of the
halting problem. Thus physical systems become non predictable -- this is a
kind of non removable essencial chaos (and constitutes the contents of Cris
Moore PhD dissertation).

Moreover, the N-body problem can solve the halting problem (in the limit of
classical reality), according to last years results on the 3-body problem on
the line ant the four and five-body problem on the plane that become
unbounded, meaning that an infinite number of events (collisions) can happen
in finite time.

Thanks,

Felix

+++++++++++++++++++++++++++++++++++++++++++++++
J. Felix Costa
Departamento de Matematica
Instituto Superior Tecnico
Av. Rovisco Pais, 1049-001 Lisboa, PORTUGAL
tel:      351 - 21 - 841 71 45
fax:     351 - 21 - 841 75 98
e-mail:   fgc at math.ist.utl.pt
www:    http://fgc.math.ist.utl.pt/jfc.htm
+++++++++++++++++++++++++++++++++++++++++++++++