🚀 go-pugleaf

In article <1992Dec15.162545.25338@news.unige.ch>, swann@divsun.unige.ch (SWANN
Philip) says:
>
>In Casti's book "Alternative Realities" there's a conjecture
>that Wolfram's classification of Cellular Automata into classes
>can be mapped into Chomsky's Hierarchy of Formal Languages. He
>cites Wolfram on this. Is there any recent work on the subject?

Cellular automata, in the unrestricted sense, have long ago been
proved to be computation universal, i.e., they can simulate any
Turing machine - see A.R. Smith III, "Simple computation-universal
cellular spaces, JACM 18(1971), 339-353.  This means, of course,
that they can also simulate any of the following: finite automata,
pushdown automata, and linear-bounded automata.  So cellular
automata can be "mapped" to the Chomsky hierarchy (if this is the
intended meaning of "mapping into the Chomsky hierarchy").

Wolfram, in "Statistical mechanics of cellular automata," Rev.
Modern Physics 55(1983),601-644, studies so-called _totalistic_
cellular automata.  In these automata, each state is considered
as a non-negative integer, and the state transition function
depends only on the sum of the states of a cell's neighborhood
(the sum includes the cell's own state).  Wolfram conjectured
that these automata are also computation-universal.

This conjecture about totalistic cellular automata was proved
true in: D. Gordon, "On the computational power of totalistic
cellular automata," Math. Systems Theory 20(1987), 43-52.
It is shown there that totalistic cellular automata can simulate
an arbitrary Turing machine in linear time - actually, twice
real time.  Needless to say, I was somewhat surprised to learn
from the above posting that this problem is still regarded by
some as a conjecture.