# 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

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

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

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

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

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

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

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

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

[Cellular automaton] rule emulations

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

States versus colors [in Turing machines]

[Methods of] encoding sequences by integers

[Universal] recursive functions

Single [universal] combinators

Cellular automaton combinators