From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
Subject: Re: Computability of the universe
Organization: Computer Science Department,  Stanford University.
Date: Tue, 15 Sep 1992 20:30:15 GMT

In article <1992Sep15.090238.186@nntp.nta.no> klaus@hal.nta.no (Klaus Gaarder FNI) writes:
>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.

To turn this negative assertion into a positive one, you are claiming
that nature can recognize some nonrecursive set, or possibly even
non-r.e. set.

Since such a set can be coded as a bit string whose i-th bit answers
question i in your list of all conceivable questions (an enumerable
set, practical languages are always assumed enumerable), this wouldn't
seem to place too much more of a demand on nature than requiring it to
be an infinite-dimensional Hilbert space: just a matter of the initial
boundary conditions happening to turn out that way.  It's certainly
mathematically possible, and if a universe like ours turns out to need
this and nothing less, then Occam's razor will strongly favor some such
theory.

If things worked this way, it would raise the interesting question of
whether it is possible for us to get to this set ourselves.  This
should be possible if the theory is at all testable.  Thus one could
pose a given question as the corresponding chaotic situation and see
what nature does with it.  This is how the Swiss watch method of
experimental physics works: smash the watches hard together and see
what falls out.  Likewise it is one way of testing job applicants: see
how they perform under stress.  There is nothing inconsistent about a
Turing machine having access to such an oracle, hence no hope of
proving mathematically that it is physically impossible by trying to
conjure up causality loops and such.

However such a boundary condition is far more complex than any
mechanism in our experience.  I, and I would imagine many others on
this list, don't really expect such will prove to be necessary to
explain the universe.  A more likely outcome to my way of thinking (and
this is not my idea, Prigogine for one if I understand him has believed
this for some time) is that nature *is* bound by the same restrictions
as Turing machines, that she does the best she can in approximating
n-body problems and other "non-computable" physics problems, but that
when the occasional "chaotic crunch" happens she is obliged to miss a
beat.

So what does "miss a beat" mean?  Well, in my extremely loose
interpretation of Prigogine (which he may want to disown if I'm being
too loose) nature doesn't want to forget too much because there's
nowhere she can go to recall it after she does.  So she tries to run a
reversible shop, one in which no information is lost in the sense that
no reachable state of the universe can have two predecessor states,
loosely speaking.  The result is mechanics, whether classical or
quantum doesn't matter in this argument.  This has the disturbing
characteristic of time symmetry: any legal behavior is still legal when
run backwards, however implausible freezing a bath of molten silver
into a tastefully tarnished Louis XIV silver chalice may sound.

My interpretaion of Prigogine's view of entropy as the result of
computational intractibility is that the universe can't always proceed
reversibly because it runs into the occasional "hot spot," the name
computer scientists use for a traffic jam in parallel computing.
Activity in a neighborhood, as measured by the quantity of energy and
momentum in an element of space-time, can build up, to a sufficient
degree that the rules for particle interaction can no longer be
followed reversibly.  A naive view of this is that a "default action"
is taken for this case, some bits of information are irretrievably lost
in that neighborhood, then things proceed normally again.

This seems to me a very plausible origin for the arrow of time: slow
entropy leakage at very occasional hot spots.

As a side effect of working out the details of such a model the
apparent teleology in the above assertion that nature is trying to
approximate the right answer disappears as nature's true, presumably
discrete, operation becomes more apparent.  At this point *our* old
continuum-based view of nature will be seen to be the approximation,
nature being by definition exactly whatever she is.  Nature might try
very hard to approximate a continuum, with lots of exception-handlers
to gracefully back out of a hot spot.  Or she might just do her own
thing with a small elegant package and it only looks
close-to-continuous to us.  I'm not aware of any experimental evidence
that would distinguish these, is anyone else (assuming you even buy my
interpretation of Prigogine)?

Nature is braver than you or me and does everything without backup
tapes.  If you work that way you have to be super careful.  If nature
didn't try very hard not to lose any information the heat death of the
universe would happen in microseconds, hot spots being very rare events
compared to normal activity.  But the heat death will happen; if any
theoretical physicists tell you that QFT predicts otherwise, I rather
doubt that Prigogine would subscribe to all details of that version of
QFT, however far Prigogine's world-view is from my interpretation.

A crude heuristic argument based on considerations of temperature and
pressure suggest that the total number of hot spots in a neighborhood
should be proportional to time multiplied by energy, having the
dimensions of Planck's constant, i.e. dimensionless when h=c=1.
Despite this suggestive connection, I am not convinced that counting
hot spots has anything to do with quantum mechanics (though Prigogine
works within quantum mechanics, necessary I imagine for a detailed
understanding of entropy but not I think for the general principle as
I'm interpreting it here).  Hot spots are the basis for entropy
independent of QM.  My intuition is that QM would look essentially
unchanged if nature suddenly learned how to get through every hot spot
without losing a beat (or a bit), only thermodynamics would look
different.

If nature had an oracle (of the appropriate Turing degree) that told
her the outcome of every hot spot, and she used it to keep all
computations reversible, we would have a world with the same quantum
mechanics and dynamics but with a reversible kind of thermodyamics.
Maybe I'm wrong about this, but the connection between hot spot number
and quantized phase space just doesn't feel right to me.

-- 
======================================================| God found the positive
Vaughan Pratt   pratt@cs.Stanford.EDU   415-494-2545  | integers, zero was
======================================================| there when He arrived.