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]

Algebraic forms [for cellular automaton rules]

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

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]