On the classifiability of cellular automata
From MaRDI portal
DOI10.1016/S0304-3975(99)00042-0zbMATH Open0947.68539arXivmath/9801152OpenAlexW2052358754MaRDI QIDQ1978505FDOQ1978505
Authors: S. Shelah, John T. Baldwin 
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: Based on computer simulations Wolfram presented in several papers conjectured classifications of cellular automata into 4 types. He distinguishes the 4 classes of cellular automata by the evolution of the pattern generated by applying a cellular automaton to a finite input. Wolfram's qualitative classification is based on the examination of a large number of simulations. In addition to this classification based on the rate of growth, he conjectured a similar classification according to the eventual pattern. We consider here one formalization of his rate of growth suggestion. After completing our major results (based only on Wolfram's work), we investigated other contributions to the area and we report the relation of some of them to our discoveries.
Full work available at URL: https://arxiv.org/abs/math/9801152
Recommendations
Cites Work
- Title not available (Why is that?)
- Computation theory of cellular automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Pattern growth in elementary cellular automata
- Machine Configuration and Word Problems of Given Degree of Unsolvability
- Measure theoretic approach to the classification of cellular automata
Cited In (18)
- Addendum to ``A mathematical classification of the one-dimensional deterministic cellular automata
- Progress, gaps and obstacles in the classification of cellular automata
- Title not available (Why is that?)
- Sub-classes and evolution stability of Wolfram's classes in the total-rule cellular automata
- Bulking II: Classifications of cellular automata
- A hierarchical classification of cellular automata
- Classification of backward filtrations and factor filtrations: examples from cellular automata
- Growing patterns in 1D cellular automata
- Cellular automata and intermediate degrees.
- Title not available (Why is that?)
- Exemples de classes d'automates cellulaires
- A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes
- Title not available (Why is that?)
- Characteristic parameters and classification of one-dimensional cellular automata
- An information-based classification of elementary cellular automata
- Title not available (Why is that?)
- Computational classification of cellular automata
- Measure theoretic approach to the classification of cellular automata
This page was built for publication: On the classifiability of cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978505)
