Notes

Chapter 3: The World of Simple Programs


Section 1: The Search for General Features


Section 2: More Cellular Automatahttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-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 Automatahttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-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 Machineshttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-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 Systemshttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-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 Systemshttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-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 Systemshttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-7--tag-systems

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

Section 8: Cyclic Tag Systemshttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-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 Machineshttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-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 Systemshttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-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 Madehttps://www.wolframscience.com/nks/chap-3--the-world-of-simple-programs--notes#sect-3-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]