real numbers and TMs

[aboulang@BBN.COM]

   Date: Fri, 15 Jan 93 10:08:24 PST
   From: Dr Michael G Dyer <dyer at cs.ucla.edu>

   Albert Boulanger, you said:

   There is a model of computation using real numbers
   that some high-powered mathematicians have developed:

      "Blum L., M. Shub, and S. Smale, "On a Theory of Computation and
      Complexity Over the Real Numbers: NP Completeness, Recursive
      Functions and Universal Machines", Bull A.M.S. 21(1989): 1-49.

      It offers a model of computing using real numbers
      more powerful than a Turing Machine.
   =======

   But is the physics of our universe only modelable in terms of
   real numbers?  e.g. is there actually an infinite amount of ever smaller space
   between any two neighboring pieces of close-together space?
   The quantum approach seems to say "no".

Good. This allows me to perhaps elevate this discussion somewhat. I
have no ready answers but allow me to outline the lines of my thinking
for the past few years.

As I mentioned in my first posting, expecting nature to have access to
the reals is a question all in itself. If nature is quantized somehow,
how can it gain access to a source of infinite algorithmic complexity?
Note that it does not need to represent a real number explicitly --
just some implicit mechanism may be good enough. I propose that *open*
computing with a heat bath may be just one way.

(I want to mention, because I believe that the questions are actually
closely related, that no one has really solved the thermodynamic arrow
of time question -- ie all dynamics, even QCD, have an outstanding
problem -- they do not explain why we go through time in one
direction. Where does the irreversibility of macroscopic systems come
from? There was a foundational paper by Michael Mackey (of
Mackey-Glass eqn fame) that is a careful delineation of possible
mechanisms that can answer the arrow-of-time question:

  "The Dyanamic Origin of Increasing Entropy"
  Michael C. Mackey, Reviews of Modern Physics, Vol 61, No. 4, October
  1989, 981-1015.

He proposes two viable mechanisms: trivial coarse graining, "taking
the trace of a lager dynamics" and coupling the system with a heat
bath.  The last option is what interests me. {One reasoen for liking
the latter is that, at the QM level, *local* hidden variable mechanisms
are ruled out} Let me state another outstanding puzzle:

  Physical chaos may be a big "con game" by nature since the
  underlying QM system is described by a linear (infinite dimensional)
  system. However, the work on QM chaos shows us that nature does a good
  job at imitating chaos. Here is a QM Chaos ref:  "Quantum Chaos", Roderick
  Jensen, Nature, Vol 355, 23 Jan 1992, 311-317.
  )


I posit, based on my investigation of asynchronous computation, that
the answer is the notion of computing with an external heat bath. The
heat bath I believe is *the* source for high algorithmic complexity
numbers in physical computing systems and why there may be in fact a
legitimate physical chaos (one needs access to the reals for true
chaos) even if QM can NOT hack it. Think of the heat bath as an
external resource of good quality bits.

One may ask about the heat bath itself. Where does it come from?
In my mind it is large part due to the asynchronous nature or concurrent
events in the real world. (Another contributor is the "nondeterminism"
of QM . This nondeterminism thing of QM is a whole other story which I
don't want to get into right now.)  This of course is a debatable
position.


   Consider a cellular automaton models, where the cell is the smallest
   quatum of space itself. ....

   I have not come upon any proof that our universe could
   not be *some sort of* cellular system (perhaps with some bizarre topography
   and bizarre, non-local "neighborhood" function).

I love these models too, but let's think about a Fredkin-type of model
with *asynchronous* dynamics. In such as system there would be a local
sense of time at each cell, and any global sense of time is an
emergent property of the macroscopic system. I believe that it may be
possible to represent infinite algorithmic complexity numbers via the
timing relationships of the cells. This is an implicit type of
representation I was alluding to above.

As I have said, this is an outline of my thoughts on the subject which
I hope illustrates to all that dismissing reals from nature and hence
dismissing a computational model like Blum, Shub, and Smale's is NOT a
trivial subject.


****************
BTW, asynchronous dynamics in artificial neural networks
is little studied. There has been work by Jacob Bahren at JPL, and John
Tsitsiklis at MIT on it, but this has been little more than applying
the "chaotic relaxation" results of fixed point type problems from the
parallel numerical analysis literature. Go for it!
****************

MIMD for the MIND,
Albert Boulanger
aboulanger at bbn.com