FOM: Precision and Turing-computability

José Félix Costa fgc at math.ist.utl.pt
Fri May 24 05:49:00 EDT 2002


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







More information about the FOM mailing list