Notes
Chapter 11: The Notion of Computation
![Efficiency of computations [in cellular automata]](/nks/notes/notes-11-2--efficiency-of-computations-in-cellular-automata/thumb.png "Efficiency of computations [in cellular automata]")
![Minimal [cellular automaton] programs for sequences](/nks/notes/notes-11-2--minimal-cellular-automaton-programs-for-sequences/thumb.png "Minimal [cellular automaton] programs for sequences")
![Other examples [of cellular automaton computation]](/nks/notes/notes-11-2--other-examples-of-cellular-automaton-computation/thumb.png "Other examples [of cellular automaton computation]")
![Random initial conditions [for squaring and primes CAs]](/nks/notes/notes-11-2--random-initial-conditions-for-squaring-and-primes-cas/thumb.png "Random initial conditions [for squaring and primes CAs]")
![[Rules for the] primes cellular automaton](/nks/notes/notes-11-2--rules-for-the-primes-cellular-automaton/thumb.png "[Rules for the] primes cellular automaton")
![[Rules for the] squaring cellular automaton](/nks/notes/notes-11-2--rules-for-the-squaring-cellular-automaton/thumb.png "[Rules for the] squaring cellular automaton")
Efficiency of computations [in cellular automata]
Minimal [cellular automaton] programs for sequences
Other examples [of cellular automaton computation]
Random initial conditions [for squaring and primes CAs]
![[Converting from CAs with] more colors](/nks/notes/notes-11-4--converting-from-cas-with-more-colors/thumb.png "[Converting from CAs with] more colors")
![Continuous systems [from cellular automata]](/nks/notes/notes-11-5--continuous-systems-from-cellular-automata/thumb.png "Continuous systems [from cellular automata]")
![Logic circuits [from cellular automata]](/nks/notes/notes-11-5--logic-circuits-from-cellular-automata/thumb.png "Logic circuits [from cellular automata]")
![Mobile automata [from cellular automata]](/nks/notes/notes-11-5--mobile-automata-from-cellular-automata/thumb.png "Mobile automata [from cellular automata]")
![Multiplication systems [from cellular automata]](/nks/notes/notes-11-5--multiplication-systems-from-cellular-automata/thumb.png "Multiplication systems [from cellular automata]")
![RAM [emulated with cellular automata]](/nks/notes/notes-11-5--ram-emulated-with-cellular-automata/thumb.png "RAM [emulated with cellular automata]")
![Register machines [from cellular automata]](/nks/notes/notes-11-5--register-machines-from-cellular-automata/thumb.png "Register machines [from cellular automata]")
![Sequential substitution systems [from cellular automata]](/nks/notes/notes-11-5--sequential-substitution-systems-from-cellular-automata/thumb.png "Sequential substitution systems [from cellular automata]")
![Substitution systems [from cellular automata]](/nks/notes/notes-11-5--substitution-systems-from-cellular-automata/thumb.png "Substitution systems [from cellular automata]")
![Turing machines [from cellular automata]](/nks/notes/notes-11-5--turing-machines-from-cellular-automata/thumb.png "Turing machines [from cellular automata]")
Continuous systems [from cellular automata]
Logic circuits [from cellular automata]
Mobile automata [from cellular automata]
Multiplication systems [from cellular automata]
RAM [emulated with cellular automata]
Register machines [from cellular automata]
Sequential substitution systems [from cellular automata]
![Arithmetic systems [emulating register machines]](/nks/notes/notes-11-6--arithmetic-systems-emulating-register-machines/thumb.png "Arithmetic systems [emulating register machines]")
![Cyclic tag systems [emulating tag systems]](/nks/notes/notes-11-6--cyclic-tag-systems-emulating-tag-systems/thumb.png "Cyclic tag systems [emulating tag systems]")
![History [of arithmetic system emulation]](/nks/notes/notes-11-6--history-of-arithmetic-system-emulation/thumb.png "History [of arithmetic system emulation]")
![Mobile automata [emulating cellular automata]](/nks/notes/notes-11-6--mobile-automata-emulating-cellular-automata/thumb.png "Mobile automata [emulating cellular automata]")
![Multicolor Turing machines [from 2-color TMs]](/nks/notes/notes-11-6--multicolor-turing-machines-from-2-color-tms/thumb.png "Multicolor Turing machines [from 2-color TMs]")
![Multiway systems [emulation]](/nks/notes/notes-11-6--multiway-systems-emulation/thumb.png "Multiway systems [emulation]")
![One-element-dependence tag systems [emulating TMs]](/nks/notes/notes-11-6--one-element-dependence-tag-systems-emulating-tms/thumb.png "One-element-dependence tag systems [emulating TMs]")
![Register machines [emulating Turing machines]](/nks/notes/notes-11-6--register-machines-emulating-turing-machines/thumb.png "Register machines [emulating Turing machines]")
![Register machines with many registers [from 2 registers]](/nks/notes/notes-11-6--register-machines-with-many-registers-from-2-registers/thumb.png "Register machines with many registers [from 2 registers]")
![Sequential substitution systems [emulating cellular automata]](/nks/notes/notes-11-6--sequential-substitution-systems-emulating-cellular-automata/thumb.png "Sequential substitution systems [emulating cellular automata]")
![Symbolic systems [emulating cellular automata]](/nks/notes/notes-11-6--symbolic-systems-emulating-cellular-automata/thumb.png "Symbolic systems [emulating cellular automata]")
![Tag systems [emulating cellular automata]](/nks/notes/notes-11-6--tag-systems-emulating-cellular-automata/thumb.png "Tag systems [emulating cellular automata]")
![Turing machines [emulating cellular automata]](/nks/notes/notes-11-6--turing-machines-emulating-cellular-automata/thumb.png "Turing machines [emulating cellular automata]")
Arithmetic systems [emulating register machines]
Computations with register machines
Cyclic tag systems [emulating tag systems]
History [of arithmetic system emulation]
Mobile automata [emulating cellular automata]
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]
Sequential substitution systems [emulating cellular automata]
Symbolic systems [emulating cellular automata]
![History [of universality in 1D cellular automata]](/nks/notes/notes-11-8--history-of-universality-in-1d-cellular-automata/thumb.png "History [of universality in 1D cellular automata]")
![Initial conditions [for rule 110]](/nks/notes/notes-11-8--initial-conditions-for-rule-110/thumb.png "Initial conditions [for rule 110]")
![Tag systems [for rule 110]](/nks/notes/notes-11-8--tag-systems-for-rule-110/thumb.png "Tag systems [for rule 110]")
![2-neighbor [class 4] rules](/nks/notes/notes-11-10--2-neighbor-class-4-rules/thumb.png "2-neighbor [class 4] rules")
![[Universal] totalistic rules](/nks/notes/notes-11-10--universal-totalistic-rules/thumb.png "[Universal] totalistic rules")
![[Universality in] 2D cellular automata](/nks/notes/notes-11-10--universality-in-2d-cellular-automata/thumb.png "[Universality in] 2D cellular automata")
![[Cellular automaton] rule emulations](/nks/notes/notes-11-11--cellular-automaton-rule-emulations/thumb.png "[Cellular automaton] rule emulations")
![Claims of non-universality [in cellular automata]](/nks/notes/notes-11-11--claims-of-non-universality-in-cellular-automata/thumb.png "Claims of non-universality [in cellular automata]")
![Encodings [of cellular automaton rules]](/nks/notes/notes-11-11--encodings-of-cellular-automaton-rules/thumb.png "Encodings [of cellular automaton rules]")
![[Structures in] rule 30](/nks/notes/notes-11-11--structures-in-rule-30/thumb.png "[Structures in] rule 30")
![[Structures in] rule 41](/nks/notes/notes-11-11--structures-in-rule-41/thumb.png "[Structures in] rule 41")
![[Structures in] rule 73](/nks/notes/notes-11-11--structures-in-rule-73/thumb.png "[Structures in] rule 73")
[Cellular automaton] rule emulations
Claims of non-universality [in cellular automata]
Encodings [of cellular automaton rules]
![History [of universal Turing machines]](/nks/notes/notes-11-12--history-of-universal-turing-machines/thumb.png "History [of universal Turing machines]")
![[Methods of] encoding sequences by integers](/nks/notes/notes-11-12--methods-of-encoding-sequences-by-integers/thumb.png "[Methods of] encoding sequences by integers")
![Minsky's [universal] Turing machine](/nks/notes/notes-11-12--minskys-universal-turing-machine/thumb.png "Minsky's [universal] Turing machine")
![Single [universal] combinators](/nks/notes/notes-11-12--single-universal-combinators/thumb.png "Single [universal] combinators")
![States versus colors [in Turing machines]](/nks/notes/notes-11-12--states-versus-colors-in-turing-machines/thumb.png "States versus colors [in Turing machines]")
![Testing universality [in symbolic systems]](/nks/notes/notes-11-12--testing-universality-in-symbolic-systems/thumb.png "Testing universality [in symbolic systems]")
![[Turing] machine 596440](/nks/notes/notes-11-12--turing-machine-596440/thumb.png "[Turing] machine 596440")
![[Universal] recursive functions](/nks/notes/notes-11-12--universal-recursive-functions/thumb.png "[Universal] recursive functions")
![[Universal] register machines](/nks/notes/notes-11-12--universal-register-machines/thumb.png "[Universal] register machines")
![[Universal] tag systems](/nks/notes/notes-11-12--universal-tag-systems/thumb.png "[Universal] tag systems")
![[Universality for] classes of systems](/nks/notes/notes-11-12--universality-for-classes-of-systems/thumb.png "[Universality for] classes of systems")
Cellular automaton combinators
History [of universal Turing machines]
[Methods of] encoding sequences by integers
Minsky's [universal] Turing machine
Single [universal] combinators
States versus colors [in Turing machines]
Testing universality [in symbolic systems]