From: jbaez@riesz.mit.edu (John C. Baez)
Subject: Re: Computability of the universe
Organization: MIT Department of Mathematics, Cambridge, MA
Date: Fri, 11 Sep 92 22:20:36 GMT

In article <BuFCLA.958@dcs.glasgow.ac.uk> jack@dcs.glasgow.ac.uk (Jack Campin) writes:
>rwallace@unix1.tcd.ie (russell wallace) wrote:
>> firth@sei.cmu.edu (Robert Firth) writes:
>>> The leap from "logic" to "Turing machines" is one I confess I'm unable
>>> to follow.  A Turing machine is merely a very simple engine that is
>>> capable of performing a very small subset of feasible computations.
>>> To deify it makes no more sense than to insist the universe must be
>>> explained using only straight edge and compasses.
>> Not so.  A Turing machine can perform any feasible computation (the
>> Church-Turing thesis).
>
>The C-T thesis is dead.  Defunct.  An ex-theory.  Have a look at this:
>
>   Type of Material: Book
>     LC Call Number: QA9.59 .P68 1989
>             Author: Pour-El, Marian B. (Marian Boykan), 1928-
>              Title: Computability in analysis and physics / Marian B. Pour-El,
>                      J. Ian Richards.
>   Publication Info: Berlin ; New York : Springer Verlag, c1989.
>  Phys. Description: x, 206 p., [1] leaf of plates : ill. ; 25 cm.
>        Series Name: Perspectives in mathematical logic
>              Notes: Bibliography: p. [195]-200.
>           Subjects: Computable functions.
>           Subjects: Mathematical analysis.
>           Subjects: Physics.
>        Other Names: Richards, J. Ian (Jonathan Ian), 1936-
>     LC Card Number:    88024880
>               ISBN: 0-387-50035-9 (U.S. : alk. paper)
>
>or the papers they wrote before that.  The basic idea is to set up
>computable boundary conditions for rather ordinary differential equations
>(like the wave equation) which do not have computable solutions.
>
>This should hardly come as a surprise if you remember that an optical
>system can do Fourier transforms in constant time.  The analogue computers
>Pour-El and Richards describe just sharpen this by solving Turing-undecidable
>problems; given how noddy Turing machines are and how complex systems
>described by differential equations are, this is not all that surprising.
>
>If you *really* want to forecast the weather accurately, get a planet, not
>a parallel processor.
>
>OK, I'm oversimplifying a bit, in that nobody can really build a Pour-El
>machine yet; but I'd bet that this work leads to real second-generation
>analogue computers some day.
>
>-- 
>--  Jack Campin    room G092, Computing Science Department, Glasgow University,
>17 Lilybank Gardens, Glasgow G12 8RZ, Scotland   TEL: 041 339 8855 x6854 (work)
>INTERNET: jack@dcs.glasgow.ac.uk or via nsfnet-relay.ac.uk    FAX: 041 330 4913
>BANG!net: via mcsun and uknet     BITNET: via UKACRL    UUCP: jack@glasgow.uucp

Great - this gives me a chance to plug a paper of mine which
appears in Pour-El and Richards; bibliography!  I've done so before 
but what the heck - this discussion seems to keep coming back.

Recursivity in quantum mechanics
Transactions of the American Mathematical Society
Vol. 280, 1983 p. 339.

This paper shows that time evolution for Schroedinger's equation is
recursive for a n-body Coulomb potential Hamiltonian.  The same
techniques would apply to all sorts of reasonable quantum mechanical
Hamiltonians.  Note that the recursivity of the time evolution of the
wavefunction does NOT contradict the fact that quantum mechanical
observations can be random, hence not computable.  The wavefunction
only determines probabilities of experimental outcomes, not the
outcomes themselves.  One could say that the result of this paper is
that any *repeatable* "computation" that one does by evolving a
wavefunction according to a reasonable Hamiltonian will be computable
by a Turing machine.

In this paper I note that Pour-El and Richards' example of a solution
of the wave equation with computable initial data and uncomputable
output is unphysical in that the uncomputability occurs only at a
SINGLE POINT of space (or with some work, a set of measure zero). 
Thus one would have to be able to measure a fields value at a SINGLE
POINT to arbitrary accuracy to use their result to build a device that
computes a non-Turing-computable function.  

What I failed to point out, since I didn't know enough about wave
equations at the time, was that if one works not with the space of C^2
solutions of the wave equation but with the physically more reasonable
space of finite-energy solutions (which is a Hilbert space, in fact),
then one can use the same techniques as in my paper to show that time
evolution for the wave equation is computable.   With this space of
solutions it makes no sense to speak of the value of the wavefunction
at a point, only certain weighted averages over small regions of space
(the "smeared field" as one says in quantum field theory - although
this is a *classical* linear wave equation).

In short, the issue of computability for wave equations depends
crucially on the precise space of solutions one works with, and a
physically more realistic space of solutions gets rid of Pour-El and
Richard's result.  So I am quite sure their effect cannot be used to
build a device.



Newsgroups: sci.physics