FOM: Precision and Turing-computability

[Martin Davis]

At 05:51 AM 5/23/2002, José Félix Costa wrote:
>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, ...

I'm familiar with Hava Siegelmann's work. It is quite misleading. Her 
neural nets provide, in effect, computable functions of the real weights. 
Since a real number can be thought of as a coded set of natural numbers, it 
is hardly surprising, that when she permit arbitrary real numbers, her nets 
generate ALL languages on a two-letter alphabet. Non-computable inputs 
produce non-computable outputs.

She proves that with rational weights she gets precisely the computable 
langages. Although she doesn't pause to observe this, the same will be true 
if the weights are limited to COMPUTABLE REALS.

The accompanying talk about a physics with infinite precision real numbers 
has no relation to the physics of serious working physicists.

Martin




                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com