Notes
Chapter 12: The Principle of Computational Equivalence
Section 1: Basic Framework https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-1--basic-framework
Section 2: Outline of the Principle https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-2--outline-of-the-principle
Section 3: The Content of the Principle https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-3--the-content-of-the-principle
Character of [general] principles [in science]
Oracles [for universal systems]
Initial conditions [as oracles]
Criteria for universality [in systems]
History [of universal objects]
Section 4: The Validity of the Principle https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-4--the-validity-of-the-principle
Section 5: Explaining the Phenomenon of Complexity https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-5--explaining-the-phenomenon-of-complexity
Section 6: Computational Irreducibility https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-6--computational-irreducibility
History [of computational irreducibility]
Amount of computation [and computational irreducibility]
More complicated rules [and reducibility]
[Examples of] reducible systems
[Computation of] mathematical functions
Formulas [and computational irreducibility]
Section 7: The Phenomenon of Free Will https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-7--the-phenomenon-of-free-will
Section 8: Undecidability and Intractability https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-8--undecidability-and-intractability
Undecidability in cellular automata
[Undecidability in] natural systems
Undecidability in tiling problems
Computational complexity theory
History [of computational complexity theory]
Lower bounds [on computational complexity]
Functions [computed by Turing machines]
Properties [of example Turing machines]
Longest halting times [in Turing machines]
Growth rates [of halting times]
[NP completeness in] natural systems
Non-deterministic Turing machines
Implementation [of TM cellular automaton]
Satisfiability [emulating Turing machines]
[Intractability in] systems of limited size
Section 9: Implications for Mathematics and Its Foundations https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-9--implications-for-mathematics-and-its-foundations
History [of concept of mathematics]
[History of] models of mathematics
Implementation [of proof example]
Substitution strategies [in proofs]
One-way transformations [as axioms]
Reducing axiom [system] details
[Mathematical] proofs in practice
Properties [of example multiway systems]
Truth and falsity [in formal systems]
Properties [of example multiway systems]
Essential incompleteness [in axiom systems]
[Universality of] predicate logic
[Universality of] algebraic axioms
Universal Diophantine equation
Statements in Peano arithmetic
[Examples of] unprovable statements
Encodings of arithmetic [by different operations]
Properties [of Diophantine equations]
Large solutions [to Diophantine equations]
Nearby powers [and integer equations]
Unsolved problems [in number theory]
More powerful axioms [for mathematics]
[Theorems about] practical programs
Rules [for multiway systems examples]
Consistency [in axiom systems]
Properties [of example multiway systems]
[Unprovable statements in] reduced arithmetic
Generators and relations [and axiom systems]
Comparison to multiway systems
Implementation [of operators from axioms]
Properties [of operators from axioms]
Algebraic systems [and operator systems]
Symbolic systems [and operator systems]
Groups and semigroups [and operator systems]
Forcing of operators [by axiom systems]
Multiway systems [and operator systems]
Properties [of logical primitives]
Notations [for logical primitives]
Theorem distributions [in standard mathematics]
Invention versus discovery in mathematics
Section 10: Intelligence in the Universe https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-10--intelligence-in-the-universe
History [of extraterrestrial life]
[Ideas of] meaning in programs
Forms of [engineered] artifacts
[Meaning in] molecular biology
Possible purposes [for systems]
Doubling rules [cellular automata]
Searching [for doubling rules]
Properties [of doubling rules]
[Rules implementing] other functions
Minimal cellular automata for sequences
Other examples [of minimal systems]
Higher perception and analysis
Messages to send [to extraterrestrials]
Science fiction [and extraterrestrials]