Notes
Chapter 3: The World of Simple Programs
![Algebraic forms [for cellular automaton rules]](/nks/notes/notes-3-2--algebraic-forms-for-cellular-automaton-rules-1/thumb.png "Algebraic forms [for cellular automaton rules]")
![Algebraic forms [for cellular automaton rules]](/nks/notes/notes-3-2--algebraic-forms-for-cellular-automaton-rules-2/thumb.png "Algebraic forms [for cellular automaton rules]")
![[Cellular automata with] two-cell neighborhoods](/nks/notes/notes-3-2--cellular-automata-with-two-cell-neighborhoods/thumb.png "[Cellular automata with] two-cell neighborhoods")
![[Cellular automaton] rules based on algebraic systems](/nks/notes/notes-3-2--cellular-automaton-rules-based-on-algebraic-systems/thumb.png "[Cellular automaton] rules based on algebraic systems")
![Common framework [for cellular automaton rules]](/nks/notes/notes-3-2--common-framework-for-cellular-automaton-rules/thumb.png "Common framework [for cellular automaton rules]")
![[History of] numbering scheme](/nks/notes/notes-3-2--history-of-numbering-scheme/thumb.png "[History of] numbering scheme")
![Mod 3 [cellular automaton] rule](/nks/notes/notes-3-2--mod-3-cellular-automaton-rule/thumb.png "Mod 3 [cellular automaton] rule")
![Numbers of [cellular automaton] rules](/nks/notes/notes-3-2--numbers-of-cellular-automaton-rules/thumb.png "Numbers of [cellular automaton] rules")
![Rule equivalences [for cellular automata]](/nks/notes/notes-3-2--rule-equivalences-for-cellular-automata/thumb.png "Rule equivalences [for cellular automata]")
![Rule expressions [for cellular automata]](/nks/notes/notes-3-2--rule-expressions-for-cellular-automata/thumb.png "Rule expressions [for cellular automata]")
![Rule orderings [for cellular automata]](/nks/notes/notes-3-2--rule-orderings-for-cellular-automata/thumb.png "Rule orderings [for cellular automata]")
![Special [cellular automaton] rules](/nks/notes/notes-3-2--special-cellular-automaton-rules/thumb.png "Special [cellular automaton] rules")
Algebraic forms [for cellular automaton rules]
Algebraic forms [for cellular automaton rules]
[Cellular automata with] two-cell neighborhoods
[Cellular automaton] rules based on algebraic systems
Common framework [for cellular automaton rules]
Compositions of cellular automata
Implementation of general cellular automata
Implementation of totalistic cellular automata
Mod 3 [cellular automaton] rule
Numbers of [cellular automaton] rules
Rule equivalences [for cellular automata]
Rule expressions [for cellular automata]
![Active cell motion [in mobile automata]](/nks/notes/notes-3-3--active-cell-motion-in-mobile-automata/thumb.png "Active cell motion [in mobile automata]")
![Compressed evolution [of mobile automata]](/nks/notes/notes-3-3--compressed-evolution-of-mobile-automata/thumb.png "Compressed evolution [of mobile automata]")
![Distribution of behavior [in mobile automata]](/nks/notes/notes-3-3--distribution-of-behavior-in-mobile-automata/thumb.png "Distribution of behavior [in mobile automata]")
![Implementation [of mobile automata]](/nks/notes/notes-3-3--implementation-of-mobile-automata/thumb.png "Implementation [of mobile automata]")
Active cell motion [in mobile automata]
Compressed evolution [of mobile automata]
Distribution of behavior [in mobile automata]
![Counter [Turing] machine](/nks/notes/notes-3-4--counter-turing-machine/thumb.png "Counter [Turing] machine")
![Distribution of behavior [in Turing machines]](/nks/notes/notes-3-4--distribution-of-behavior-in-turing-machines/thumb.png "Distribution of behavior [in Turing machines]")
![Head motion [in Turing machines]](/nks/notes/notes-3-4--head-motion-in-turing-machines/thumb.png "Head motion [in Turing machines]")
![History [of Turing machines]](/nks/notes/notes-3-4--history-of-turing-machines/thumb.png "History [of Turing machines]")
![Implementation [of Turing machines]](/nks/notes/notes-3-4--implementation-of-turing-machines/thumb.png "Implementation [of Turing machines]")
![Localized structures [in Turing machines]](/nks/notes/notes-3-4--localized-structures-in-turing-machines/thumb.png "Localized structures [in Turing machines]")
![Number of [Turing machine] rules](/nks/notes/notes-3-4--number-of-turing-machine-rules/thumb.png "Number of [Turing machine] rules")
![Numbering scheme [for Turing machines]](/nks/notes/notes-3-4--numbering-scheme-for-turing-machines/thumb.png "Numbering scheme [for Turing machines]")
Distribution of behavior [in Turing machines]
Head motion [in Turing machines]
Implementation [of Turing machines]
Localized structures [in Turing machines]
![2D representations [of substitution systems]](/nks/notes/notes-3-5--2d-representations-of-substitution-systems/thumb.png "2D representations [of substitution systems]")
![Connections [of substitution systems] with digit sequences](/nks/notes/notes-3-5--connections-of-substitution-systems-with-digit-sequences/thumb.png "Connections [of substitution systems] with digit sequences")
![Connections [of substitution systems] with square roots](/nks/notes/notes-3-5--connections-of-substitution-systems-with-square-roots/thumb.png "Connections [of substitution systems] with square roots")
![Growth rates [in substitution systems]](/nks/notes/notes-3-5--growth-rates-in-substitution-systems/thumb.png "Growth rates [in substitution systems]")
![History [of substitution systems]](/nks/notes/notes-3-5--history-of-substitution-systems/thumb.png "History [of substitution systems]")
![Implementation [of substitution systems]](/nks/notes/notes-3-5--implementation-of-substitution-systems/thumb.png "Implementation [of substitution systems]")
![Other examples [of substitution systems]](/nks/notes/notes-3-5--other-examples-of-substitution-systems/thumb.png "Other examples [of substitution systems]")
![Properties [of substitution systems]](/nks/notes/notes-3-5--properties-of-substitution-systems/thumb.png "Properties [of substitution systems]")
![Representation [of substitution systems] by paths](/nks/notes/notes-3-5--representation-of-substitution-systems-by-paths/thumb.png "Representation [of substitution systems] by paths")
2D representations [of substitution systems]
Connections [of substitution systems] with digit sequences
Connections [of substitution systems] with square roots
Generalized Fibonacci sequences
Growth rates [in substitution systems]
History [of substitution systems]
Implementation [of substitution systems]
Other examples [of substitution systems]
Properties [of substitution systems]
![Capabilities [of sequential substitution systems]](/nks/notes/notes-3-6--capabilities-of-sequential-substitution-systems/thumb.png "Capabilities [of sequential substitution systems]")
![History [of sequential substitution systems]](/nks/notes/notes-3-6--history-of-sequential-substitution-systems/thumb.png "History [of sequential substitution systems]")
![Implementation [of sequential substitution systems]](/nks/notes/notes-3-6--implementation-of-sequential-substitution-systems/thumb.png "Implementation [of sequential substitution systems]")
![Order of replacements [in sequential substitution systems]](/nks/notes/notes-3-6--order-of-replacements-in-sequential-substitution-systems/thumb.png "Order of replacements [in sequential substitution systems]")
Capabilities [of sequential substitution systems]
History [of sequential substitution systems]
![History [of tag systems]](/nks/notes/notes-3-7--history-of-tag-systems/thumb.png "History [of tag systems]")
![Implementation [of tag systems]](/nks/notes/notes-3-7--implementation-of-tag-systems/thumb.png "Implementation [of tag systems]")
![Randomness [in tag systems]](/nks/notes/notes-3-7--randomness-in-tag-systems/thumb.png "Randomness [in tag systems]")
![Generalizations [of cyclic tag systems]](/nks/notes/notes-3-8--generalizations-of-cyclic-tag-systems/thumb.png "Generalizations [of cyclic tag systems]")
![History [of cyclic tag systems]](/nks/notes/notes-3-8--history-of-cyclic-tag-systems/thumb.png "History [of cyclic tag systems]")
![Implementation [of cyclic tag systems]](/nks/notes/notes-3-8--implementation-of-cyclic-tag-systems/thumb.png "Implementation [of cyclic tag systems]")
![Mechanical implementation [of cyclic tag systems]](/nks/notes/notes-3-8--mechanical-implementation-of-cyclic-tag-systems/thumb.png "Mechanical implementation [of cyclic tag systems]")
![Properties [of cyclic tag systems]](/nks/notes/notes-3-8--properties-of-cyclic-tag-systems/thumb.png "Properties [of cyclic tag systems]")
Generalizations [of cyclic tag systems]
History [of cyclic tag systems]
Implementation [of cyclic tag systems]
![Extended instruction sets [for register machines]](/nks/notes/notes-3-9--extended-instruction-sets-for-register-machines/thumb.png "Extended instruction sets [for register machines]")
![Halting [of register machines]](/nks/notes/notes-3-9--halting-of-register-machines/thumb.png "Halting [of register machines]")
![History [of register machines]](/nks/notes/notes-3-9--history-of-register-machines/thumb.png "History [of register machines]")
![Implementation [of register machines]](/nks/notes/notes-3-9--implementation-of-register-machines/thumb.png "Implementation [of register machines]")
Extended instruction sets [for register machines]
Halting [of register machines]
History [of register machines]
![[Enumerating] possible expressions](/nks/notes/notes-3-10--enumerating-possible-expressions/thumb.png "[Enumerating] possible expressions")
![History [of symbolic systems]](/nks/notes/notes-3-10--history-of-symbolic-systems/thumb.png "History [of symbolic systems]")
![Implementation [of symbolic systems]](/nks/notes/notes-3-10--implementation-of-symbolic-systems/thumb.png "Implementation [of symbolic systems]")
![Long halting times [in symbolic systems]](/nks/notes/notes-3-10--long-halting-times-in-symbolic-systems/thumb.png "Long halting times [in symbolic systems]")
![Network analogs [of symbolic systems]](/nks/notes/notes-3-10--network-analogs-of-symbolic-systems/thumb.png "Network analogs [of symbolic systems]")
![Order dependence [in symbolic systems]](/nks/notes/notes-3-10--order-dependence-in-symbolic-systems/thumb.png "Order dependence [in symbolic systems]")
![Other [symbolic systems] rules](/nks/notes/notes-3-10--other-symbolic-systems-rules/thumb.png "Other [symbolic systems] rules")
![Properties [of example symbolic system]](/nks/notes/notes-3-10--properties-of-example-symbolic-system/thumb.png "Properties [of example symbolic system]")
![Representations [for symbolic expressions]](/nks/notes/notes-3-10--representations-for-symbolic-expressions/thumb.png "Representations [for symbolic expressions]")
![Trees [representation for symbolic systems]](/nks/notes/notes-3-10--trees-representation-for-symbolic-systems/thumb.png "Trees [representation for symbolic systems]")
[Enumerating] possible expressions
Implementation [of symbolic systems]
Long halting times [in symbolic systems]
Network analogs [of symbolic systems]
Order dependence [in symbolic systems]
Other [symbolic systems] rules
Properties [of example symbolic system]
![Practicalities [of computer experiments]](/nks/notes/notes-3-12--practicalities-of-computer-experiments/thumb.png "Practicalities [of computer experiments]")
History of experimental mathematics
Practicalities [of computer experiments]