FOM: Re: Computability and Physics
John Case
case at eecis.udel.edu
Wed Nov 26 17:53:25 EST 1997
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.
More information about the FOM
mailing list