FOM: Wolfram and logic/foundations of mathematics

[John T. Baldwin]

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).