FOM: Re: Computability and Physics

[John Case]

Joe,

Thanks!  I uudecoded your essay and converted it to a Unix-friendly format for
my reading pleasure.  

You may be interested in my _brief_ discussions of a discrete universe with
computable statistically expected behavior.  Such discussions may be found, 
for example, in \cite{C87} (http://www.cis.udel.edu/~case/papers/tms-f93.ps)
and in \cite{C98} (http://www.cis.udel.edu/~case/papers/mkamst-tr.ps).
A discrete quantum mechanical universe (perhaps our own universe) is likely
one of these. See \cite{dMSS56} for the relevant, fundamental (and
constructive) result that Turing machines with random oracle with a computable 
probability distribution have (partially) computable _expected_ I/O behavior.

(-8 John

  ****************************************************************************
  * John Case                                      Email: case at cis.udel.edu  *
  * Professor                                      Phone: +1-302-831-2714 or *
  * Computer and Information Sciences Department          +1-302-831-4175    *
  * 101A Smith Hall                                  FAX: +1-302-831-8458    *
  * University of Delaware                                                   *
  * Newark, DE 19716-2586 (USA)                     Home: +1-302-832-5557    *
  *                   URL:  http://www.cis.udel.edu/~case                    *
  ****************************************************************************

                               REFERENCES

\bibitem[Cas87]{C87}
J.~Case.
\newblock Turing machine.
\newblock In Stuart Shapiro, editor, {\em Encyclopedia of Artificial
  Intelligence}. John Wiley and Sons, New York, NY, 1987.
 
\bibitem[Cas98]{C98}
J.~Case.
\newblock The power of vacillation in language learning.
\newblock {\em {SIAM} Journal on Computing}, 1998.
\newblock To appear.

\bibitem[dMSS56]{dMSS56}
K.~deLeeuw, E.~Moore, C.~Shannon, and N.~Shapiro.
\newblock Computability by probabilistic machines.
\newblock {\em Automata Studies, Annals of Math. Studies}, 34:183--212, 1956.