FOM: Re: non-computable waves

[Jeffrey Ketland]

Klaus Weihrauch wrote:

>Pour-El and Richards have defined a 3-dimensional wave
>u(x,t) such that the amlitude u(x,0) at time 0 is computable and
>the amlitude u(x,1) at time 1 is (continuous but) not computable
>(in both cases computable real functions according
>to Grzegorczyk's definition).

Their monograph is:

Pour-El, M. & Richards, J.I 1989: "Computability and Analysis in Physics"
(Perspectives in Mathematical Logic, Springer-Verlag)

I've been trying to read this (in my very amateurish way) for a few months.
This is my understanding (which is sorely testing my crude mathematical
abilities):

The crucial theorem that Professor Weihrauch refers to is Theorem 6, p. 116,
applied to the D'Alembert wave equation ([d/dx)^2 + (d/dy)^2 + (d/dz)^2 -
(d/dt)^2]u(x,y,z,t) = 0).
Theorem 6 depends upon the First Main Theorem (p. 101) which roughly says
that bounded operators preserve computability (i.e., map computable elements
to computable elements) and unbounded operators don't.

Also, the authors emphasize that this result (that a computable initial
function u(x, 0) can evolve into a non-computable function u(x, 1)) depends
upon using the "Uniform Norm" for the functions involved (i.e,. the norm of
f is sup(|f(x)| wrt x).
The authors note (Theorem 7) that if the "Energy norm" is used, then
computable initial data always evolve into computable functions. (The energy
norm of a wave u(x, t) is a measure of the energy in the wave: it is the
supremum w.r.t time t of the space-integral of [(Grad(u))^2 + (du/dt)^2]).
The authors state "... the question of whether an operator preserves
computability depends upon the norm--and hence the Banach space--being
considered" (p. 95).

Also, the Heat Equation behaves differently to the Wave Equation: the
evolution operator is bounded, and the First Main Theorem implies that
computable initial conditions give a computable solution (Theorem 8, p.
119).

I don't pretend in the slightest to fully understand this stuff or to have
worked through the details. I don't know if this kind of work has been
further developed by anyone else recently. I'd be interested to know. In
particular, it would be interesting to know what happens with the
conventional Schroedinger equation (which is more like the Heat Equation,
but with "imaginary time"), the Dirac equation (which is first-order in
derivatives) and the on-linear field equations for General Relativity.
(Roughly, it seems to involve checking whether the appropriate evolution
operator is bounded or not and then applying the First Main Theorem. Topics
for your graduate students ....).

>Can this theorem be used for designing a "wave computer"
>which beats the Turing machine (i.e., computes a number function
>which is not Turing computable)?
>
>Probably many people have thought about it.
>Is there a definitive satisfactory answer?
>

There are several people on FOM list who have contributed ideas about this
sort of thing. (Joe Shipman has said many interesting things - care to add
anything more, Joe?). Speaking from my realist position, I see no a priori
reason why

    (a) non-computable physical processes shouldn't exist in Nature
    (b) such processes might not be harnessable by humans to build machines
which "physically compute" non recursive functions.

For example, it conceivable that it might be possible to build some kind of
"Arithmetical Truth Machine": a machine, which when given any formula of
arithmetic as input, computes its truth value (in some finite time).

Although that sounds like pure sci-fi, that sort of thing would have
fascinating (pro-realism, I'd say) consequences for f.o.m and philosophy of
mathematics.


Jeff Ketland

Jeffrey Ketland
Lecturer
Dept of Philosophy, University of Nottingham
Nottingham NG7 2RD United Kingdom
Tel: 0115 951 5843
Home: 0115 922 3978
E-mail: jeffrey.ketland at nottingham.ac.uk
Home: ketland at ketland.fsnet.co.uk





>
>
>
>
>Name: Klaus Weihrauch
>Position: Professor of Computer Science
>Institution: Fernuniversitaet Hagen
>Research interest: Computablity
>More information: http://www.math.psu.edu/simpson/
>
>