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
================================================================================
More information about the FOM
mailing list