From: klaus@hal.nta.no (Klaus Gaarder FNI)
Subject: Re: Computability of the universe
Organization: Norwegian Telecom Research
Date: Tue, 15 Sep 92 09:02:38 GMT

In article <1992Sep11.013141.28378@galois.mit.edu>, jbaez@riesz.mit.edu (John C. Baez) writes:
|> In article <1992Sep10.183603.2357@sei.cmu.edu> firth@sei.cmu.edu (Robert
|> Firth) writes: 
|> >In article <rwallace.716144999@unix1.tcd.ie> rwallace@unix1.tcd.ie
|> (russell wallace) writes: 
|> 
|> >>Not so. A Turing machine can perform any feasible computation (the
|> >>Church-Turing thesis).
|> 
|> >Yes, I know the thesis.  The argument is circular, because it defines
|> >"feasible" to mean "capable of being computed by a <machine equivalent
|> >to> a Turing machine".  
|> 
|> This is rather unfair to Church and Turing, and I'm crossposting to
|> sci.math and sci.logic so you can be properly flamed.  :-)  Hopefully
|> you know that you're being unfair.  These guys aren't famous for
|> proposing "A Turing machine can do any computation that can be done by
|> any machine which can do precisely those computations that can be done
|> by a Turing machine"!  Roughly speaking, their thesis is that a Turing
|> machine can do any computation that can be done by a systematic,
|> repeatable procedure.  It required a lot of work to gather enough
|> evidence for this thesis that it is now generally regarded as true.
|> 
|> >Unfortunately, a true random number is not
|> >one of the things so computable, though it can of course be computed
|> >using one of several flavours of the universal quantum computer.
|> 
|> Do you have any detailed references on a "universal quantum computer"?
|> 
|> In any event, I agree that quantum theory as generally accepted allows
|> us to build machines that can produce bit sequences not computable by a
|> Turing machine.  (Really one should read the archives; last year we
|> discussed the practical difficulties involving noise etc. and the
|> difficulties of checking whether your "quantum random sequence
|> generator" is working according to specs.)  Of course, such a machine
|> will not produce the same such sequence repeatedly, so the Church-Turing
|> thesis is not violated.  

Hi there,
the above fragment of a discussion apperears to me to be about whether "nature" is
computable or not (yes?). This is an extremely intriguing question the answer of
which has profound consequences. Having read some papers on the subject some time
ago I will share some references and comments with the rest of the world.

Classical Physics:
------------------
	The so-called "three body problem", computing the trajectory of three
(yes only 3) bodies under mutual gravitational (Newton-style) interaction, is not
computable.

	A cellular automaton based on classical elastic collisons of hard
"billiard-balls" easily provides a universal computer (the ref is Fredkin, Physica
 D10, 1986 (or '85)).

	An intriguing model of computation (the basis for the above mentioned CA)
called "Conservative Logic" by Fredkin and Toffoli may be found in an issue of 
"Int.Journ. on Theoretical Physics", vol 21, nos 3/4 (?). This is one of three
issues reporting from a Los-Alamos workshop on physics and computation, providing
really stimulating  reading!!

Thermodynamics:
---------------
	There are interesting studies on the limits of computation with regards
to thermodynamics (entropy etc). For instance the Fredkin-Toffoli paper above
provides a clue that computation is not inherently irreversible, which C.H.Bennet
has gone on to prove with a universal turing machine working infinitely slow....

Quantum Computing:
------------------
	Even if Heisenberg and Pauli are trying to put sand in the gears, I can
remember a reference by an author Deutch(?) on the subject of quantum computers.
I cannot remember the exact title, I shall try to find the paper in my "archive"
.... (arch-pile is more like it).

My personal hunch is that nature is NOT computable, and I believe it should be
fairly easy to indicate why. The three-body problem gives us a clue as to the
complexity of interactions in nature. The Church-Turing thesis has nothing to do
with this as pointed out in the inclusion above.

-- 
    __o   
  _`\<,_  
 (*)/ (*) Claudio Caputti
+++++++++++++++++++++++++++++++++++++++^++++++++++++++++++++++++++++++++++++++
Free will - the result of chaotic amplification of quantum events in the brain.
------------------------------------------------------------------------------