# Notes

# Chapter 12: The Principle of Computational Equivalence

## Section 1: Basic Frameworkhttps://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-1--basic-framework

## Section 2: Outline of the Principlehttps://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 Principlehttps://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 Principlehttps://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 Complexityhttps://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-5--explaining-the-phenomenon-of-complexity

## Section 6: Computational Irreducibilityhttps://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 Willhttps://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence--notes#sect-12-7--the-phenomenon-of-free-will

## Section 8: Undecidability and Intractabilityhttps://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 Foundationshttps://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 Universehttps://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]