CA as Turing Machines: (m (states), n (symbols))

Rule 110 is a 2,5 UTM ?

Alex Smith’s (possibly flawed) proof of a CA as 2,3 UTM, which would be the simplest since a 2,2 UTM provably cannot be universal:
2 states and 3 colors, number 596440 in Wolfram’s numbering scheme.
There are 2,985,984 possible 2,3 machines.

Raymond Kurzweil’s review of Wolfram’s work:
In summary, Wolfram’s sweeping and ambitious treatise paints a compelling but ultimately overstated and incomplete picture. Wolfram joins a growing community of voices that believe that patterns of information, rather than matter and energy, represent the more fundamental building blocks of reality.

Notes on Lawrence Gray’s review of Wolfram’s “A New Kind of Science”.

[My comments in square brackets]

Gray:

According to Wolfram, “traditional” mathematics and science are doomed: mathematics because of its emphasis on rigorous proof, and science because of its preference for models that can make accurate predictions. He says that the most interesting problems presented by nature are likely to be formally undecidable or computationally irreducible

[very like Kauffman]

The “Principle of Computational Equivalence”, which we are told is a “new law of nature” that “has vastly richer implications than…any [other] single collection of laws in science” (ANKS, pp. 720 and 726). The entire final chapter of the book is devoted to this principle, but, surprisingly, Wolfram does not provide us with a definitive statement of it. Here is my attempt, pieced together from various phrases in Chapter12 of ANKS: Except for those trajectories that are obviously simple, almost all of the trajectories of a (natural or theoretical) dynamical system can be viewed as computations of equivalent sophistication, which is to say that they are universal (see ANKS, pp. 716–9).

Thus, if you observe a trajectory of some system, such as a CA or a differential equation or the weather or even a bucket of rusting nails, then either you will see something that is obviously simple, or else arbitrarily complex computations will pass before your eyes.

i.e principal of computational equivaence = everything non trivial is equally (and maximally complicated) complicated enough to be a universal turing machine

He is particularly hard on chaos theory, which he more or less reduces to a trivial observation about sensitive
dependence on initial conditions: “Indeed, all that it shows is that if there is complexity in the details of the initial conditions, then this complexity will eventually appear in the large-scale behavior of the system”

Particularly impressive is the chapter where he attempts to capture modern physics, including relativity theory and quantum mechanics, in a CA-like system.

3. Book review by Scott Aaronson for Quantum Information and Computing, September 2002.
(Proves that Wolfram’s proposed discrete model for the universe cannot accommodate both special relativity and Bell’s inequality violations.)

Universal CAs
It turns out that there is more than one kind of universality. So far we have talked about only the kind that primarily concerns Wolfram, which is the ability to simulate arbitrary Turing machines. But there is something known as a Universal CA, or UCA, that can do more. A UCA with lattice Λ must be able to simulate every other CA with lattice Λ. Furthermore, the space and time “costs” of the simulation must be bounded above by constant multiples of the space and time requirements of the CA being simulated. What is the difference between simulating an arbitrary Turing machine and simulating an arbitrary CA? A Turing machine is essentially a computer with a single processor (the head), whereas a CA is a computer with infinitely many parallel processors (the cells). So even a universal Turing machine with an infinite tape cannot actually simulate a CA; it can simulate only larger and larger portions of it at a slower and slower pace.

I think it highly unlikely that Rule 110 is a UCA, although I have no proof. On the other hand, there are some explicit constructions, such as David Bell’s so-called “Unit Life Cell”, that seem to indicate that the “Game of Life” is a UCA. So there is a precise, mathematical sense in which the Game of Life is capable of performing more sophisticated computations than appear to be possible for Rule 110, contrary to the Principle of Computational Equivalence.

One of Wolfram’s main themes is that complicated mechanisms (such as Darwinian natural selection) are not required for explaining the complexity observed in nature.

[huh? the set of all CAs is equivalent to a natural selection model – inheritance, rule (mutation to discover the appropriate rule) etc.]

Most of the known UCAs, such as the Game of Life, are extremely sensitive to errors. Randomly changing the color of a single cell is often enough to turn an elaborate construction like Paul Rendell’s Life Turing machine into garbage. It seems highly unlikely that the Game of Life can carry on any sort of nontrivial simulation if it is subjected to random errors, even if the errors are quite rare. In other words, I do not believe that the software exists that can make some natural version of the Game of Life reliably simulate a complex living organism. A fault-tolerant universal CAis a UCA whose ability to simulate other CAs is not affected by random color changes throughout the lattice, provided such “errors” are sufficiently sparse. The existence of such systems was proved by Peter Gacs

(they are all compex)

But such a construction does not seem like something that would easily arise in nature. Thus, it is not clear that nature could easily find a mechanism that behaves like a fault-tolerant UCA without some “guiding hand” like natural selection. But Wolfram’s thesis seems to require nature to do just that. Until someone finds a simple fault tolerant UCA, the main theme of ANKS remains wishful speculation.