Notes

Chapter 11: The Notion of Computation

Section 1: Computation as a Frameworkhttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-1--computation-as-a-framework

History of computing

Practical computers

Intuition from practical computing

Section 2: Computations in Cellular Automatahttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-2--computations-in-cellular-automata

Other examples [of cellular automaton computation]

[Rules for the] squaring cellular automaton

[Rules for the] primes cellular automaton

Random initial conditions [for squaring and primes CAs]

Efficiency of computations [in cellular automata]

Minimal [cellular automaton] programs for sequences

Section 3: The Phenomenon of Universalityhttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-3--the-phenomenon-of-universality

History of universality

Universality in Mathematica

Section 4: A Universal Cellular Automatonhttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-4--a-universal-cellular-automaton

Universal cellular automaton

[Converting from CAs with] more colors

Section 5: Emulating Other Systems with Cellular Automatahttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-5--emulating-other-systems-with-cellular-automata

Mobile automata [from cellular automata]

Turing machines [from cellular automata]

Substitution systems [from cellular automata]

Sequential substitution systems [from cellular automata]

Register machines [from cellular automata]

Multiplication systems [from cellular automata]

Continuous systems [from cellular automata]

Logic circuits [from cellular automata]

RAM [emulated with cellular automata]

Section 6: Emulating Cellular Automata with Other Systemshttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-6--emulating-cellular-automata-with-other-systems

Mobile automata [emulating cellular automata]

Turing machines [emulating cellular automata]

Sequential substitution systems [emulating cellular automata]

Tag systems [emulating cellular automata]

Symbolic systems [emulating cellular automata]

Cyclic tag systems [emulating tag systems]

Multicolor Turing machines [from 2-color TMs]

One-element-dependence tag systems [emulating TMs]

Register machines [emulating Turing machines]

Register machines with many registers [from 2 registers]

Computations with register machines

Arithmetic systems [emulating register machines]

History [of arithmetic system emulation]

Multiway systems [emulation]

Section 7: Implications of Universality

Section 8: The Rule 110 Cellular Automatonhttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-8--the-rule-110-cellular-automaton

History [of universality in 1D cellular automata]

Initial conditions [for rule 110]

Tag systems [for rule 110]

Section 9: The Significance of Universality in Rule 110

Section 10: Class 4 Behavior and Universalityhttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-10--class-4-behavior-and-universality

2-neighbor [class 4] rules

[Universal] totalistic rules

[Universality in] 2D cellular automata

Section 11: The Threshold of Universality in Cellular Automatahttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-11--the-threshold-of-universality-in-cellular-automata

Claims of non-universality [in cellular automata]

[Structures in] rule 73

[Structures in] rule 30

[Structures in] rule 41

[Cellular automaton] rule emulations

Encodings [of cellular automaton rules]

Logic operations and universality

Section 12: Universality in Turing Machines and Other Systemshttps://www.wolframscience.com/nks/chap-11--the-notion-of-computation--notes#sect-11-12--universality-in-turing-machines-and-other-systems

Minsky's [universal] Turing machine

History [of universal Turing machines]

Rule 110 Turing machines

Rule 60 Turing machines

Turing machine enumeration

States versus colors [in Turing machines]

[Turing] machine 596440

[Universal] tag systems

[Methods of] encoding sequences by integers

[Universal] register machines

[Universal] recursive functions

Lambda calculus

Combinator properties

Single [universal] combinators

Cellular automaton combinators

Testing universality [in symbolic systems]

Criteria for universality

[Universality for] classes of systems