FOM: Re: Computability and Physics

John Case case at
Wed Nov 26 17:53:25 EST 1997


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} (
and in \cite{C98} (
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  *
  * 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:                    *


\newblock Turing machine.
\newblock In Stuart Shapiro, editor, {\em Encyclopedia of Artificial
  Intelligence}. John Wiley and Sons, New York, NY, 1987.
\newblock The power of vacillation in language learning.
\newblock {\em {SIAM} Journal on Computing}, 1998.
\newblock To appear.

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.

More information about the FOM mailing list