FOM: Precision and Turing-computability

[José Félix Costa]

[Please replace ''above'' in the last paragraph by ''below''. I am sending
this note, because other people have received the message as it stands
below.]

Martin Davis wrote:

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

The inputs are not non-computable. They are finite and satisfying classical
constraints. ARRNs are seen as high-dimensional dynamical system. What is
addressed is not the possibility of recognizing all languages but the fact
that P/poly coincides with with ARNNs computing in polynomial time.
I am not saying that such a compter is physicaly realizable.

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

She does in Kolmogorov complexity of ARNNs together with Ricard Gevaldá.
Computable reals improve complexity. This was a conjecture of David Harel
some years ago.

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

I am sure that if you can embed hypercomputation in maxwel equations, this
is rather interesting and has nothing to do with the possibility of
measuring real-valued parameters. it has to do with the nature of physical
models and not with observables. This is related to Penrose question: is the
intrinsic nature of physical models computable or not computable.
!!Shannon's GPAC!! work in theory with !real parameters!. However his
computational power is above Turing. If you interesting I can send you the
thesis of one of my students about this issue.

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