Selected problems in the theory of classical cellular automata

In the book we present certain results of the work we have done in the theory of Classical Cellular Automata (CA). At present, these results form an essential constituent of the CA problematics. In particular, we have studied such problems as the nonconstructability problem in the CA, the decomposition problem of global transition functions in the CA, extremal constructive possibilities, the parallel formal grammars and languages defined by CA, complexity of finite configurations and global transition functions in the CA, simulation problem in classical CA, etc. At present, the CA problematics is a rather well developed independent field of the mathematical cybernetics that has a rather considerable field of various appendices. In addition, with the equal right the CA problematics can be considered as a component of such fields as discrete parallel dynamical systems, discrete mathematics, cybernetics, complex systems and some others. In our viewpoint, the book will represent an indubit

• Math
• Science

								
Introduction
Chapter 1. The basic concepts of classical cellular automata
Chapter 2. Nonconstructability problem in classical cellular automata (classical CA models)
2.1. Preliminary information on the CA problems
2.2. The nonconstructability types for classical CA models
2.3. Existence criteria of the basic nonconstructability types in classical CA models
2.4. The nonconstructability problem for finite CA models and CA models on splitting
2.5. The reversibility problem of dynamics of classical CA models
2.6. Algorithmical aspects of the nonconstructability problem and some connected questions of dynamics of classical CA models
Chapter 3. Extremal constructive opportunities of classical cellular automata
3.1. Universal finite configurations in classical CA models
3.2. Self–reproduction of finite configurations in classical CA models
Chapter 4. The complexity problem of finite configurations in classical CA models
Chapter 5. Parallel formal grammars and languages determined by classical cellular automata (CA models)
5.1. The basic properties of the parallel languages, determined by classical cellular automata
5.2. Parallel grammars determined by classical CA models in comparison with formal grammars of some other classes and types
5.3. Parallel grammars defined by nondeterministic CA models
5.4. Algorithmical problems of the theory of parallel grammars, determined by classical CA models
Chapter 6. The modelling problem in classical cellular automata (CA) along with the related questions
6.1. Concepts of modelling in classical CA
6.2. Modelling of the well–known formal processing algorithms of words in finite alphabets by means of CA models
6.3. Simulating of classical CA models by means of CA models of the same class
6.4. The formal parallel algorithms determined by classical one–dimensional CA models
6.5. Special questions of simulating in classical CA models concerning their dynamics
6.6. Sketch on sofrware oriented on CA simulating
Chapter 7. The decomposition problem of global transition functions in classical CA models
7.1. Decomposition of special global transition functions in classical CA models
7.2. Some approaches to solution of the general decomposition problem of global transition functions
7.3. Questions of solvability of the decomposition problem for global transition functions of CA models
7.4. The complexity problem for global transition functions in classical CA models
Chapter 8. Certain applied aspects of the CA problematics
8.1. Solution of the Steinhaus combinatory problem
8.2. Solution of the Ulam problem from number theory
8.3. Certain applied aspects of CA models in biological sciences
Conclusion
References
About the authors
								Rate this book:4.0 / 2 votes