FOM: non-computable waves

[Prof. Weihrauch]

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