𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the classifiability of cellular automata

✍ Scribed by John T. Baldwin; Saharon Shelah

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
106 KB
Volume
230
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Based on computer simulations Wolfram presented in several papers conjectured classiΓΏcations of cellular automata into four types. We show a natural formalization of his rate of growth suggestion does not provide a classiΓΏcation (even probabilistically) of all cellular automata: For any rational p; q; 06p; q 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.

πŸ“œ SIMILAR VOLUMES

Alternation on cellular automata
Alternation on cellular automata
✍ MartΓ­n Matamala πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 819 KB
On computing the entropy of cellular aut
On computing the entropy of cellular automata
✍ Michele D'amico; Giovanni Manzini; Luciano Margara πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 208 KB

We study the topological entropy of a particular class of dynamical systems: cellular automata. The topological entropy of a dynamical system (X; F) is a measure of the complexity of the dynamics of F over the space X . The problem of computing (or even approximating) the topological entropy of a gi

Remarks on permutive cellular automata
Remarks on permutive cellular automata
✍ J.-P. Allouche; G. Skordev πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 164 KB

We prove that every two-dimensional permutive cellular automaton is conjugate to a one-sided shift with compact set of states.

Fast one-way cellular automata
Fast one-way cellular automata
✍ Andreas Klein; Martin Kutrib πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 333 KB

Space-bounded one-way cellular language acceptors (OCA) are investigated. The only inclusion known to be strict in their time hierarchy from real-time to exponential-time is between real-time and linear-time! We show the surprising result that there exists an inΓΏnite hierarchy of properly included O