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 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]