This textbook presents analytic methods and results for exploring and understanding cellular automata and discrete neural networks. The book includes exercises and bibliographies and may serve also as a reference manual.

Inhalt

1. Turing Computability and Complexity.- 1.1 Models of Sequential Computation.- 1.2 Complexity.- 1.3 Cellular Machines.- 1.4 Prerequisites.- References.- 2. Cellular Automata.- 2.1 Finite-State Automata.- 2.2 Regular Graphs.- 2.3 Local Rules and Global Maps.- 2.4 Fundamental Questions.- 2.5 Notation.- 2.6 Problems.- 2.7 Notes.- References.- 3. Linear Cellular Automata.- 3.1 Linear Rules.- 3.2 Basic Properties.- 3.3 Global Dynamics via Fractals.- 3.4 The Role of Linear Rules.- 3.5 Problems.- 3.6 Notes.- References.- 4. Semi-totalistic Automata.- 4.1 Semi-totalistic Rules.- 4.2 Construction and Computation Universality.- 4.3 Restricted Totalistic Rules.- 4.4 Threshold Automata.- 4.5 Problems.- 4.6 Notes.- References.- 5. Decision Problems.- 5.1 Algorithmic and Dynetic Problems.- 5.2 ID Euclidean Automata.- 5.3 2D Euclidean Automata.- 5.4 Noneuclidean Automata.- 5.5 Complexity Questions.- 5.6 Problems.- 5.7 Notes.- References.- 6. Neural and Random Boolean Networks.- 6.1 Types of Generalizations.- 6.2 Other Parallel Models.- 6.3 Summary of Results.- 6.4 Proofs.- 6.5 Problems.- 6.6 Notes.- References.- 7. General Properties.- 7.1 Metric Preliminaries.- 7.2 Basic Results.- 7.3 Injeetivity, Surjectivity and Local Reversibility.- 7.4 Some Generalizations.- 7.5 Problems.- 7.6 Notes.- References.- 8. Classification.- 8.1 Finite Networks.- 8.2 Wolfram Classification.- 8.3 Classification via Limit Sets.- 8.4 Mean Field Theory.- 8.5 Local Structure Theory.- 8.6 Other Classifications.- 8.7 Problems.- 8.8 Notes.- References.- 9. Asymptotic Behavior.- 9.1 Linear Rules.- 9.2 Exact Solution.- 9.3 Simulation in Continuous Systems.- 9.4 Observability.- 9.5 Problems.- 9.6 Notes.- References.- 10. Some Inverse Problems.- 10.1 Signals and Synchronization.- 10.2 Formal Language Recognition.-10.3 Picture Languages.- 10.4 Problems.- 10.5 Notes.- References.- 11. Real Computation.- 11.1 Representation and Primitives.- 11.2 Exact Computation.- 11.3 Approximate Computation by Neural Nets.- 11.4 Problems.- 11.5 Notes.- References.- 12. A Bibliography of Applications.- 12.1 Physics.- 12.2 Chemistry.- 12.3 Biology.- 12.4 Computer Science.- 12.5 Artificial Intelligence and Cognitive Science.- 12.6 Miscellaneous.- References.- Author Index.- Symbol Index.