[FOM] Wolfram Cellular Automata versus Turing Machines

[John T. Baldwin]

Cellular automata differ from (linearly bounded) automata because they 
operate in parallel, simulaneously updating every
cell on an infinite tape.  There are certainly cellular automata which 
are universal in the strictest possible sense.  The exciting and
somewhat controversial claim is the particularly simple rule 110  (a 1 
dimensional, 2 state, radius 1) ca is universal.

I posted a lengthy discussion with references about a year ago.  It is 
available at http://www2.math.uic.edu/~jbaldwin/model.html
or in the fom archives.  I am more optimistic about the Cook result now 
than when I wrote that note and should post an update soon.

Steve Stevenson wrote:

>Good afternoon,
>
>When Wolfram first started with the CA work in the mid 80s, I seem to
>recall that they were shown to be equivalent to linear bounded
>automata. Is that right? And if not, may I please have a reference to
>a proof of what they really are?
>
>best,
>steve
>  
>