Solvable Cellular Automata
Methods and Applications
Buch in deiner Nähe kaufen
Beschreibung
The main focus of the book is solvability of cellular automata, that is, expressing the state of a given cell after a given number of steps by an explicit formula. The author considers solutions of two types of initial value problems for cellular automata, the deterministic one and the probabilistic one. In the first chapter the basic concepts of cellular automata theory are introduced. Deterministic initial value problem is introduced next and solutions for selected simple rules are also presented. In the following chapters various techniques for solving the deterministic problem are introduced, using elementary CA rules of increasing complexity as examples. The second part of the book introduces the concept of probability measure in the context of cellular automata and the probabilistic initial value problem for both deterministic and probabilistic rules. The book is amply illustrated with examples and applications such as the density classification problem, phase transitions in traffic models or the diffusion of innovations model. In the appendix, solution formulae (both deterministic and probabilistic) for over 60 elementary cellular automata rules are listed. Ruelle-Frobenius-Perron equations for all 88 minimal elementary cellular automata are also provided.
The main focus of the book is solvability of cellular automata, that is, expressing the state of a given cell after a given number of steps by an explicit formula. The author considers solutions of two types of initial value problems for cellular automata, the deterministic one and the probabilistic one. In the first chapter the basic concepts of cellular automata theory are introduced. Deterministic initial value problem is introduced next and solutions for selected simple rules are also presented. In the following chapters various techniques for solving the deterministic problem are introduced, using elementary CA rules of increasing complexity as examples. The second part of the book introduces the concept of probability measure in the context of cellular automata and the probabilistic initial value problem for both deterministic and probabilistic rules. The book is amply illustrated with examples and applications such as the density classification problem, phase transitions in traffic models or the diffusion of innovations model. In the appendix, solution formulae (both deterministic and probabilistic) for over 60 elementary cellular automata rules are listed. Ruelle-Frobenius-Perron equations for all 88 minimal elementary cellular automata are also provided.
Addresses solvability of cellular automata with many results and applications Provides an appendix with solution formulas, both deterministic and probabilistic, for over 60 cellular automata Provides a quick overview table which are solvable in both deterministic and probabilistic sense
Autor*in
Henryk Fukś
Themen in »Solvable Cellular Automata«
Density of ones in Cellular Automata Solutions of Cellular Automata Density Classification Problem Traffic Rule Local Structure Theory Block Probabilities Orbit of Bernoulli Measure
Stimmen zu »Solvable Cellular Automata«
“I also liked very much the organization of the content. Notation, figures, and tables are listed in the first pages. Each chapter has its own bibliography. The appendices constitute a useful reference on ECA properties.” (Silvio Capobianco, Mathematical Reviews, August, 2025)
()