Chapter 3: The World of Simple Programs

Section 1: The Search for General Features

Section 2: More Cellular Automata

[History of] numbering scheme Rule equivalences [for cellular automata] Special [cellular automaton] rules Rule expressions [for cellular automata] Rule orderings [for cellular automata] Algebraic forms [for cellular automaton rules] Rule 150 Rule 225 Rule 22 Algebraic forms [for cellular automaton rules] Rule 45 Rule 73 Alternating colors [Cellular automata with] two-cell neighborhoods Numbers of [cellular automaton] rules Implementation of general cellular automata Implementation of totalistic cellular automata Common framework [for cellular automaton rules] Mod 3 [cellular automaton] rule Compositions of cellular automata [Cellular automaton] rules based on algebraic systems

Section 3: Mobile Automata

Implementation [of mobile automata] Compressed evolution [of mobile automata] Distribution of behavior [in mobile automata] Active cell motion [in mobile automata] Implementation of generalized mobile automata

Section 4: Turing Machines

Implementation [of Turing machines] Number of [Turing machine] rules Numbering scheme [for Turing machines] Counter [Turing] machine Distribution of behavior [in Turing machines] Head motion [in Turing machines] Localized structures [in Turing machines] History [of Turing machines]

Section 5: Substitution Systems

Implementation [of substitution systems] Properties [of substitution systems] Growth rates [in substitution systems] Fibonacci numbers Lucas numbers Generalized Fibonacci sequences Connections [of substitution systems] with digit sequences Connections [of substitution systems] with square roots Spectra of substitution systems Representation [of substitution systems] by paths Paperfolding sequences 2D representations [of substitution systems] Other examples [of substitution systems] History [of substitution systems]

Section 6: Sequential Substitution Systems

Implementation [of sequential substitution systems] Capabilities [of sequential substitution systems] Order of replacements [in sequential substitution systems] History [of sequential substitution systems]

Section 7: Tag Systems

Implementation [of tag systems] Randomness [in tag systems] History [of tag systems]

Section 8: Cyclic Tag Systems

Implementation [of cyclic tag systems] Generalizations [of cyclic tag systems] Mechanical implementation [of cyclic tag systems] Properties [of cyclic tag systems] History [of cyclic tag systems]

Section 9: Register Machines

Implementation [of register machines] Halting [of register machines] Extended instruction sets [for register machines] History [of register machines] Random programs

Section 10: Symbolic Systems

Implementation [of symbolic systems] Symbolic expressions Representations [for symbolic expressions] [Enumerating] possible expressions Properties [of example symbolic system] Other [symbolic systems] rules Long halting times [in symbolic systems] Trees [representation for symbolic systems] Order dependence [in symbolic systems] History [of symbolic systems] Operator systems Network analogs [of symbolic systems]

Section 11: Some Conclusions

Section 12: How the Discoveries in This Chapter Were Made

Repeatability and numerical analysis Studying simple systems The relevance of theorems Attitudes of mathematicians History of experimental mathematics Practicalities [of computer experiments]

From Stephen Wolfram: A New Kind of Science [citation]