Chapter 11: The Notion of Computation

Section 1: Computation as a Framework

History of computing Practical computers Intuition from practical computing

Section 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 Universality

History of universality Universality in Mathematica

Section 4: A Universal Cellular Automaton

Universal cellular automaton [Converting from CAs with] more colors

Section 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 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 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 Universality

2-neighbor [class 4] rules [Universal] totalistic rules [Universality in] 2D cellular automata

Section 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 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 Combinators Combinator properties Single [universal] combinators  Cellular automaton combinators Testing universality [in symbolic systems] Criteria for universality [Universality for] classes of systems

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