# FOM: non-computable waves

Prof. Weihrauch Klaus.Weihrauch at FernUni-Hagen.de
Fri Sep 15 04:41:53 EDT 2000

Some weeks ago I have asked:

> Date: Mon, 21 Aug 2000 14:48:25 +0200 (MET DST)
> From: Klaus.Weihrauch at FernUni-Hagen.de (Prof. Weihrauch)
> To: fom at math.psu.edu
> Subject: FOM: non-computable waves
>
> 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).
>
> 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?
>

In the following discussion the most concrete answer has been
given by Joe Shipman (Aug 22)  who cites his 1992 paper:

> ...
> However, this doesn't lead to a  violation of Church's thesis because
> their result does not lead to any physically realizable experiments
> (one would have to somehow specify initial conditions to
> infinite precision).
> ...

This encouraged me to revise the last section of the paper
K.Weihrauch and Ning Zhong, The wave propagator is Turing computable'' (1998)
and to give a more detailed explanation.
It reads as follows but probably cannot be fully understood
without the context in the paper.

================================================
We return to the question for a wave computer which beats the Turing
machine and ask, whether these results can be used to construct a
physical device computing a number function $h:\IN\to \IN$ which is
not Turing computable. We consider 3 dimensional waves from $C(\IR^3)$
or $C^1(\IR^3)$ as states which propagate according to the wave equation
($\ast\ast$) and assume that amplitude boxes as well as amplitude
boxes of the partial derivatives (for differentiable states) can
be observed. We discuss 3 attempts.

(1) We would like to start propagation with the $\delta_3$-computable
wave $f_{\rm PR}\in C^1(\IR^3)$ of the Pour-El/Richards counter example.
This function is defined by an infinite r.e. set of  atomic properties
$A\in \sigma_3$. Since in accordance with our model only finitely many
of them can be guaranteed by measurement, it is impossible to prepare
$f_{\rm PR}$ at time $0$ exactly.

(2) As an alternative we perform experiments $i=1,2,\ldots$ with initial
conditions $f_i\in C^1(\IR^3)$ satifying the first $i$ properties
$A\in \sigma_3$ of  $f_{\rm PR}$ in some fixed computable enumeration.
Although the sequence $i\mapsto f_i$ converges to  $f_{\rm PR}$
w.r.t. the topology $\tau_3$, the sequence $i\mapsto S_1(f_i)$
in general does not converge (w.r.t. the topology $\tau_3$), since
(the wave propagator) $S_1$ is not $(\tau_3,\tau_3)$-continuous.
Therefore, performing measurements on the $S_1(f_i)$ at time $1$ is useless.

(3) As a further alternative we would like to perform experiments
$i=1,2,\ldots$ with initial conditions $g_i\in C^1(\IR^3)$ satifying the
first $i$ properties $A\in \sigma^1_3$ of  $f_{\rm PR}$
(amplitude boxes of $f_{\rm PR}$ and its partial derivative)
in some fixed enumeration. Since $S_1$ is $(\tau^1_3,\tau_3)$-continuous,
the sequence $i\mapsto S_1(g_i)$ converges (w.r.t. $\tau_3$)
to $S_1(f_{\rm PR})$, which is not $\delta_3$-computable.
So by repeated measurements at time 1 it might be possible to
find a $\delta_3$-name of  $S_1(f_{\rm PR})$, which is a
non-computable discrete function.
Unfortunately,  the function $f_{\rm PR}$ is not $\delta^1_3$-computable, and
so we are not able to enumerate the properties $A\in \sigma^1_3$ of
$f_{\rm PR}$ effectively.

In summary, even under very idealizing assumptions about measurements,
it seems to be very unlikely that the Pour-El/Richards
counter-example can be used to build a physical machine with a
wave subroutine'' computing  a function which is not Turing computable.
We may still believe that the Church/Turing Thesis holds.
===============================================================

(1) is Joe Shipman's argument. (2) and (3) consider two different types
physical measurement each of which induces a topology
( $\tau_3$ on $C(\IR^3)$ and $\tau^1_3(\IR^3)$ on $C^1(\IR^3)$ )
and a concept of computability in the mathematical model.

Of course, it is not clear how much must be said to explain
satisfactorily ''  why some physical experiment is impossible.

Jeffrey Ketland wrote:

> From owner-fom at math.psu.edu Wed Aug 23 20:21:14 2000
> ........

> I thought a bit about applying the Pour-El/Richards ideas to the
> (non-relativistic) Quantum Mechanics case
>
> 1. Quantum mechanics time evolution
>
> In the last post, I mentioned the problem of applying Pour-El/Richards 1st
> Main Theorem (bounded operators preserve computability, unbounded ones
> don't). to the QM case (i.e. Schroedinger equation). The Schroedinger
> equation is
>
>     (1) H  f(x,t)  =  ih (d/dt) f(x,t)
>
> where f is a wave-function in the Hilbert space (usually L^2[R]) and H is
> the Hamiltonian operator on the Hilbert space.
> ................

In a recent paper Turing Computability of the Schroedinger Propagator''
(to be presented at CCA-2000 in Swansea, 17 - 19 September 2000)
Ning Zhong proves that the Schroedinger propagator $S$ for a single particle
mapping $(t,f,g)$, where $f$ is the initial state and $g$ is the
external force, to the state at time $t$ is computable (on $L^2(\IR^3)$
with an approriate concept of computability which is closely
related to a concept of measurement).

Therefore, also in this situation future states seem to be computable
by Turing machines.

================================================================================
Prof. Dr. Klaus Weihrauch             tel: (02331) 987-2722
Theoretische Informatik I             fax: (02331) 987-319
Universitaet Hagen                  email: klaus.weihrauch at fernuni-hagen.de
D 58084 HAGEN
GERMANY

http://www.informatik.fernuni-hagen.de/import/thi1/klaus.weihrauch
================================================================================