auto
small
medium
large
x-large
Notes
Chapter 11
Jump to page
Lookup in index
Search
‹
›
Notes
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
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
There are no notes for this section.
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
There are no notes for this section.
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