FOM: Wolfram and logic/foundations of mathematics
John T. Baldwin
jbaldwin at uic.edu
Wed Jun 5 21:59:11 EDT 2002
Henry Cohn writes, `He (Wolfram) conjectures that (roughly) almost all
systems are either computationally universal or obviously not
computationally universal (because they do something trivial). '
I haven't read the most recent book but the paper On the
classifiability of Cellular Automata, by myself and Saharon Shelah
addresses a similar early conjecture by Wolfram. Here is the
abstract of our paper:
Based on computer simulations Wolfram presented in several papers
conjectured classifications of cellular automata into 4 types.
We show a natural formalization of his rate of growth suggestion does
not provide a classification (even probabilistically) of all
cellular automata. Theorem. For any rational $p$, $q$, $0 \leq
p,q \leq =1$ with $p+q =1$, there is a cellular automata
$A_{p,q}$ which has probability $p$ of being in class 3,
probability $q$ of being in class 4. We also construct an automata
which grows monotonically at rate $\log t$, rather than at a
constant rate.
The paper is available on my website
http://www.math.uic.edu/~jbaldwin/model.html or Shelah's at
Rutgers. It appeared in the Journal of Theoretical Computer
Science Journal of Theoretical Computer Science 230 (2000) 117-129
I have found considerable imprecision in the Cellular Automata
literature about the distinction between simulation and universal
computability. In particular, the significance of input-output
conventions is glossed over (noted I believe also in Kadvnay's
post).
More information about the FOM
mailing list