Notes
Chapter 12: The Principle of Computational Equivalence
![[History of] Church's Thesis](/nks/notes/notes-12-2--history-of-churchs-thesis/thumb.png "[History of] Church's Thesis")
![History [of PCE]](/nks/notes/notes-12-2--history-of-pce/thumb.png "History [of PCE]")
![Note for mathematicians [about PCE]](/nks/notes/notes-12-2--note-for-mathematicians-about-pce/thumb.png "Note for mathematicians [about PCE]")
![Block occurrences [in rule 30]](/nks/notes/notes-12-3--block-occurrences-in-rule-30/thumb.png "Block occurrences [in rule 30]")
![Character of [general] principles [in science]](/nks/notes/notes-12-3--character-of-general-principles-in-science/thumb.png "Character of [general] principles [in science]")
![[Construction of] universal objects](/nks/notes/notes-12-3--construction-of-universal-objects/thumb.png "[Construction of] universal objects")
![Criteria for universality [in systems]](/nks/notes/notes-12-3--criteria-for-universality-in-systems/thumb.png "Criteria for universality [in systems]")
![Encodings [for universality]](/nks/notes/notes-12-3--encodings-for-universality/thumb.png "Encodings [for universality]")
![History [of universal objects]](/nks/notes/notes-12-3--history-of-universal-objects/thumb.png "History [of universal objects]")
![Initial conditions [as oracles]](/nks/notes/notes-12-3--initial-conditions-as-oracles/thumb.png "Initial conditions [as oracles]")
![Oracles [for universal systems]](/nks/notes/notes-12-3--oracles-for-universal-systems/thumb.png "Oracles [for universal systems]")
Block occurrences [in rule 30]
Character of [general] principles [in science]
[Construction of] universal objects
Criteria for universality [in systems]
History [of universal objects]
Initial conditions [as oracles]
![Emulating discrete systems [with continuous ones]](/nks/notes/notes-12-4--emulating-discrete-systems-with-continuous-ones/thumb.png "Emulating discrete systems [with continuous ones]")
![Human thinking [and PCE]](/nks/notes/notes-12-4--human-thinking-and-pce/thumb.png "Human thinking [and PCE]")
![Initial conditions [and continuity]](/nks/notes/notes-12-4--initial-conditions-and-continuity/thumb.png "Initial conditions [and continuity]")
![[Time compression in] ODEs](/nks/notes/notes-12-4--time-compression-in-odes/thumb.png "[Time compression in] ODEs")
![[Universality in] equations](/nks/notes/notes-12-4--universality-in-equations/thumb.png "[Universality in] equations")
![Amount of computation [and computational irreducibility]](/nks/notes/notes-12-6--amount-of-computation-and-computational-irreducibility/thumb.png "Amount of computation [and computational irreducibility]")
![[Computation of] mathematical functions](/nks/notes/notes-12-6--computation-of-mathematical-functions/thumb.png "[Computation of] mathematical functions")
![[Examples of] reducible systems](/nks/notes/notes-12-6--examples-of-reducible-systems/thumb.png "[Examples of] reducible systems")
![[Examples of] short computations](/nks/notes/notes-12-6--examples-of-short-computations/thumb.png "[Examples of] short computations")
![Formulas [and computational irreducibility]](/nks/notes/notes-12-6--formulas-and-computational-irreducibility/thumb.png "Formulas [and computational irreducibility]")
![History [of computational irreducibility]](/nks/notes/notes-12-6--history-of-computational-irreducibility/thumb.png "History [of computational irreducibility]")
![[History of] exact solutions](/nks/notes/notes-12-6--history-of-exact-solutions/thumb.png "[History of] exact solutions")
![More complicated rules [and reducibility]](/nks/notes/notes-12-6--more-complicated-rules-and-reducibility/thumb.png "More complicated rules [and reducibility]")
Amount of computation [and computational irreducibility]
[Computation of] mathematical functions
[Examples of] reducible systems
[Examples of] short computations
Formulas [and computational irreducibility]
History [of computational irreducibility]
![[Free] will and purpose](/nks/notes/notes-12-7--free-will-and-purpose/thumb.png "[Free] will and purpose")
![History [of ideas about free will]](/nks/notes/notes-12-7--history-of-ideas-about-free-will/thumb.png "History [of ideas about free will]")
![Responsibility [and free will]](/nks/notes/notes-12-7--responsibility-and-free-will/thumb.png "Responsibility [and free will]")
![Source of [free] will](/nks/notes/notes-12-7--source-of-free-will/thumb.png "Source of [free] will")
![[Classes of] fast algorithms](/nks/notes/notes-12-8--classes-of-fast-algorithms/thumb.png "[Classes of] fast algorithms")
![[Computational complexity of] finding outcomes](/nks/notes/notes-12-8--computational-complexity-of-finding-outcomes/thumb.png "[Computational complexity of] finding outcomes")
![Functions [computed by Turing machines]](/nks/notes/notes-12-8--functions-computed-by-turing-machines/thumb.png "Functions [computed by Turing machines]")
![Growth rates [of halting times]](/nks/notes/notes-12-8--growth-rates-of-halting-times/thumb.png "Growth rates [of halting times]")
![History [of computational complexity theory]](/nks/notes/notes-12-8--history-of-computational-complexity-theory/thumb.png "History [of computational complexity theory]")
![History [of undecidability]](/nks/notes/notes-12-8--history-of-undecidability/thumb.png "History [of undecidability]")
![Implementation [of TM cellular automaton]](/nks/notes/notes-12-8--implementation-of-tm-cellular-automaton/thumb.png "Implementation [of TM cellular automaton]")
![[Intractability in] systems of limited size](/nks/notes/notes-12-8--intractability-in-systems-of-limited-size/thumb.png "[Intractability in] systems of limited size")
![Longest halting times [in Turing machines]](/nks/notes/notes-12-8--longest-halting-times-in-turing-machines/thumb.png "Longest halting times [in Turing machines]")
![Lower bounds [on computational complexity]](/nks/notes/notes-12-8--lower-bounds-on-computational-complexity/thumb.png "Lower bounds [on computational complexity]")
![[NP completeness in] natural systems](/nks/notes/notes-12-8--np-completeness-in-natural-systems/thumb.png "[NP completeness in] natural systems")
![[One-sided] Turing machines](/nks/notes/notes-12-8--one-sided-turing-machines/thumb.png "[One-sided] Turing machines")
![Properties [of example Turing machines]](/nks/notes/notes-12-8--properties-of-example-turing-machines/thumb.png "Properties [of example Turing machines]")
![Satisfiability [emulating Turing machines]](/nks/notes/notes-12-8--satisfiability-emulating-turing-machines/thumb.png "Satisfiability [emulating Turing machines]")
![[Turing] machine 1507](/nks/notes/notes-12-8--turing-machine-1507/thumb.png "[Turing] machine 1507")
![[Turing] machine 600720](/nks/notes/notes-12-8--turing-machine-600720/thumb.png "[Turing] machine 600720")
![[Undecidability in] natural systems](/nks/notes/notes-12-8--undecidability-in-natural-systems/thumb.png "[Undecidability in] natural systems")
[Computational complexity of] finding outcomes
Computational complexity theory
Functions [computed by Turing machines]
Growth rates [of halting times]
History [of computational complexity theory]
Implementation [of TM cellular automaton]
[Intractability in] systems of limited size
Longest halting times [in Turing machines]
Lower bounds [on computational complexity]
Non-deterministic Turing machines
[NP completeness in] natural systems
Properties [of example Turing machines]
Satisfiability [emulating Turing machines]
Undecidability in cellular automata
[Undecidability in] natural systems
![Algebraic systems [and operator systems]](/nks/notes/notes-12-9--algebraic-systems-and-operator-systems/thumb.png "Algebraic systems [and operator systems]")
![[Axioms for] arithmetic](/nks/notes/notes-12-9--axioms-for-arithmetic/thumb.png "[Axioms for] arithmetic")
![[Axioms for] geometry](/nks/notes/notes-12-9--axioms-for-geometry/thumb.png "[Axioms for] geometry")
![[Axioms for] real analysis](/nks/notes/notes-12-9--axioms-for-real-analysis/thumb.png "[Axioms for] real analysis")
![Basic logic [and axioms]](/nks/notes/notes-12-9--basic-logic-and-axioms/thumb.png "Basic logic [and axioms]")
![Consistency [in axiom systems]](/nks/notes/notes-12-9--consistency-in-axiom-systems/thumb.png "Consistency [in axiom systems]")
![Encodings of arithmetic [by different operations]](/nks/notes/notes-12-9--encodings-of-arithmetic-by-different-operations/thumb.png "Encodings of arithmetic [by different operations]")
![Essential incompleteness [in axiom systems]](/nks/notes/notes-12-9--essential-incompleteness-in-axiom-systems/thumb.png "Essential incompleteness [in axiom systems]")
![[Examples of] unprovable statements](/nks/notes/notes-12-9--examples-of-unprovable-statements/thumb.png "[Examples of] unprovable statements")
![Fields [and axioms]](/nks/notes/notes-12-9--fields-and-axioms/thumb.png "Fields [and axioms]")
![Forcing of operators [by axiom systems]](/nks/notes/notes-12-9--forcing-of-operators-by-axiom-systems/thumb.png "Forcing of operators [by axiom systems]")
![Frameworks [in mathematics]](/nks/notes/notes-12-9--frameworks-in-mathematics/thumb.png "Frameworks [in mathematics]")
![General topology [and axioms]](/nks/notes/notes-12-9--general-topology-and-axioms/thumb.png "General topology [and axioms]")
![Generators and relations [and axiom systems]](/nks/notes/notes-12-9--generators-and-relations-and-axiom-systems/thumb.png "Generators and relations [and axiom systems]")
![Groups [and axioms]](/nks/notes/notes-12-9--groups-and-axioms/thumb.png "Groups [and axioms]")
![Groups and semigroups [and operator systems]](/nks/notes/notes-12-9--groups-and-semigroups-and-operator-systems/thumb.png "Groups and semigroups [and operator systems]")
![Growth rates [of functions]](/nks/notes/notes-12-9--growth-rates-of-functions/thumb.png "Growth rates [of functions]")
![History [of concept of mathematics]](/nks/notes/notes-12-9--history-of-concept-of-mathematics/thumb.png "History [of concept of mathematics]")
![History [of logic axioms]](/nks/notes/notes-12-9--history-of-logic-axioms/thumb.png "History [of logic axioms]")
![[History of] models of mathematics](/nks/notes/notes-12-9--history-of-models-of-mathematics/thumb.png "[History of] models of mathematics")
![[History of] truth tables](/nks/notes/notes-12-9--history-of-truth-tables/thumb.png "[History of] truth tables")
![Implementation [of operators from axioms]](/nks/notes/notes-12-9--implementation-of-operators-from-axioms/thumb.png "Implementation [of operators from axioms]")
![Implementation [of proof example]](/nks/notes/notes-12-9--implementation-of-proof-example/thumb.png "Implementation [of proof example]")
![Large solutions [to Diophantine equations]](/nks/notes/notes-12-9--large-solutions-to-diophantine-equations/thumb.png "Large solutions [to Diophantine equations]")
![[Mathematical] proofs in practice](/nks/notes/notes-12-9--mathematical-proofs-in-practice/thumb.png "[Mathematical] proofs in practice")
![[Methods for] proof searching](/nks/notes/notes-12-9--methods-for-proof-searching/thumb.png "[Methods for] proof searching")
![More powerful axioms [for mathematics]](/nks/notes/notes-12-9--more-powerful-axioms-for-mathematics/thumb.png "More powerful axioms [for mathematics]")
![Multiway systems [and operator systems]](/nks/notes/notes-12-9--multiway-systems-and-operator-systems/thumb.png "Multiway systems [and operator systems]")
![Nearby powers [and integer equations]](/nks/notes/notes-12-9--nearby-powers-and-integer-equations/thumb.png "Nearby powers [and integer equations]")
![Notations [for logical primitives]](/nks/notes/notes-12-9--notations-for-logical-primitives/thumb.png "Notations [for logical primitives]")
![One-way transformations [as axioms]](/nks/notes/notes-12-9--one-way-transformations-as-axioms/thumb.png "One-way transformations [as axioms]")
![Ordering of [mathematical] constructs](/nks/notes/notes-12-9--ordering-of-mathematical-constructs/thumb.png "Ordering of [mathematical] constructs")
![Properties [of Diophantine equations]](/nks/notes/notes-12-9--properties-of-diophantine-equations/thumb.png "Properties [of Diophantine equations]")
![Properties [of example multiway systems]](/nks/notes/notes-12-9--properties-of-example-multiway-systems-1/thumb.png "Properties [of example multiway systems]")
![Properties [of example multiway systems]](/nks/notes/notes-12-9--properties-of-example-multiway-systems-2/thumb.png "Properties [of example multiway systems]")
![Properties [of example multiway systems]](/nks/notes/notes-12-9--properties-of-example-multiway-systems-3/thumb.png "Properties [of example multiway systems]")
![Properties [of logical primitives]](/nks/notes/notes-12-9--properties-of-logical-primitives/thumb.png "Properties [of logical primitives]")
![Properties [of operators from axioms]](/nks/notes/notes-12-9--properties-of-operators-from-axioms/thumb.png "Properties [of operators from axioms]")
![Real algebra [and axioms]](/nks/notes/notes-12-9--real-algebra-and-axioms/thumb.png "Real algebra [and axioms]")
![Reducing axiom [system] details](/nks/notes/notes-12-9--reducing-axiom-system-details/thumb.png "Reducing axiom [system] details")
![Rings [and axioms]](/nks/notes/notes-12-9--rings-and-axioms/thumb.png "Rings [and axioms]")
![Rules [for multiway systems examples]](/nks/notes/notes-12-9--rules-for-multiway-systems-examples/thumb.png "Rules [for multiway systems examples]")
![Searching for logic [axioms]](/nks/notes/notes-12-9--searching-for-logic-axioms/thumb.png "Searching for logic [axioms]")
![Semigroups [and axioms]](/nks/notes/notes-12-9--semigroups-and-axioms/thumb.png "Semigroups [and axioms]")
![Set theory [and axioms]](/nks/notes/notes-12-9--set-theory-and-axioms/thumb.png "Set theory [and axioms]")
![Substitution strategies [in proofs]](/nks/notes/notes-12-9--substitution-strategies-in-proofs/thumb.png "Substitution strategies [in proofs]")
![Symbolic systems [and operator systems]](/nks/notes/notes-12-9--symbolic-systems-and-operator-systems/thumb.png "Symbolic systems [and operator systems]")
![[The concept of] infinity](/nks/notes/notes-12-9--the-concept-of-infinity/thumb.png "[The concept of] infinity")
![Theorem distributions [in standard mathematics]](/nks/notes/notes-12-9--theorem-distributions-in-standard-mathematics/thumb.png "Theorem distributions [in standard mathematics]")
![[Theorems about] practical programs](/nks/notes/notes-12-9--theorems-about-practical-programs/thumb.png "[Theorems about] practical programs")
![Truth and falsity [in formal systems]](/nks/notes/notes-12-9--truth-and-falsity-in-formal-systems/thumb.png "Truth and falsity [in formal systems]")
![Two-operator logic [axioms]](/nks/notes/notes-12-9--two-operator-logic-axioms/thumb.png "Two-operator logic [axioms]")
![[Universality of] algebraic axioms](/nks/notes/notes-12-9--universality-of-algebraic-axioms/thumb.png "[Universality of] algebraic axioms")
![[Universality of] predicate logic](/nks/notes/notes-12-9--universality-of-predicate-logic/thumb.png "[Universality of] predicate logic")
![[Universality of] set theory](/nks/notes/notes-12-9--universality-of-set-theory/thumb.png "[Universality of] set theory")
![[Unprovable statements in] reduced arithmetic](/nks/notes/notes-12-9--unprovable-statements-in-reduced-arithmetic/thumb.png "[Unprovable statements in] reduced arithmetic")
![Unsolved problems [in number theory]](/nks/notes/notes-12-9--unsolved-problems-in-number-theory/thumb.png "Unsolved problems [in number theory]")
Algebraic systems [and operator systems]
Comparison to multiway systems
Consistency [in axiom systems]
Encodings of arithmetic [by different operations]
Essential incompleteness [in axiom systems]
[Examples of] unprovable statements
Forcing of operators [by axiom systems]
Generators and relations [and axiom systems]
Groups and semigroups [and operator systems]
History [of concept of mathematics]
[History of] models of mathematics
Implementation [of operators from axioms]
Implementation [of proof example]
Invention versus discovery in mathematics
Large solutions [to Diophantine equations]
[Mathematical] proofs in practice
More powerful axioms [for mathematics]
Multiway systems [and operator systems]
Nearby powers [and integer equations]
Notations [for logical primitives]
One-way transformations [as axioms]
Ordering of [mathematical] constructs
Properties [of Diophantine equations]
Properties [of example multiway systems]
Properties [of example multiway systems]
Properties [of example multiway systems]
Properties [of logical primitives]
Properties [of operators from axioms]
Reducing axiom [system] details
Rules [for multiway systems examples]
Statements in Peano arithmetic
Substitution strategies [in proofs]
Symbolic systems [and operator systems]
Theorem distributions [in standard mathematics]
[Theorems about] practical programs
Truth and falsity [in formal systems]
Universal Diophantine equation
[Universality of] algebraic axioms
[Universality of] predicate logic
![Detection methods [for SETI]](/nks/notes/notes-12-10--detection-methods-for-seti/thumb.png "Detection methods [for SETI]")
![Doubling rules [cellular automata]](/nks/notes/notes-12-10--doubling-rules-cellular-automata/thumb.png "Doubling rules [cellular automata]")
![Forms of [engineered] artifacts](/nks/notes/notes-12-10--forms-of-engineered-artifacts/thumb.png "Forms of [engineered] artifacts")
![History [of extraterrestrial life]](/nks/notes/notes-12-10--history-of-extraterrestrial-life/thumb.png "History [of extraterrestrial life]")
![[History of] SETI](/nks/notes/notes-12-10--history-of-seti/thumb.png "[History of] SETI")
![[Ideas of] meaning in programs](/nks/notes/notes-12-10--ideas-of-meaning-in-programs/thumb.png "[Ideas of] meaning in programs")
![[Meaning in] molecular biology](/nks/notes/notes-12-10--meaning-in-molecular-biology/thumb.png "[Meaning in] molecular biology")
![Messages to send [to extraterrestrials]](/nks/notes/notes-12-10--messages-to-send-to-extraterrestrials/thumb.png "Messages to send [to extraterrestrials]")
![Other examples [of minimal systems]](/nks/notes/notes-12-10--other-examples-of-minimal-systems/thumb.png "Other examples [of minimal systems]")
![P versus NP [and messages]](/nks/notes/notes-12-10--p-versus-np-and-messages/thumb.png "P versus NP [and messages]")
![Possible purposes [for systems]](/nks/notes/notes-12-10--possible-purposes-for-systems/thumb.png "Possible purposes [for systems]")
![Practical arguments [about exterrestrials]](/nks/notes/notes-12-10--practical-arguments-about-exterrestrials/thumb.png "Practical arguments [about exterrestrials]")
![Properties [of doubling rules]](/nks/notes/notes-12-10--properties-of-doubling-rules/thumb.png "Properties [of doubling rules]")
![[Rules implementing] other functions](/nks/notes/notes-12-10--rules-implementing-other-functions/thumb.png "[Rules implementing] other functions")
![Science fiction [and extraterrestrials]](/nks/notes/notes-12-10--science-fiction-and-extraterrestrials/thumb.png "Science fiction [and extraterrestrials]")
![Searching [for doubling rules]](/nks/notes/notes-12-10--searching-for-doubling-rules/thumb.png "Searching [for doubling rules]")
Doubling rules [cellular automata]
Forms of [engineered] artifacts
Higher perception and analysis
History [of extraterrestrial life]
[Ideas of] meaning in programs
[Meaning in] molecular biology
Messages to send [to extraterrestrials]
Minimal cellular automata for sequences
Other examples [of minimal systems]
Possible purposes [for systems]
Practical arguments [about exterrestrials]
Properties [of doubling rules]
[Rules implementing] other functions
Science fiction [and extraterrestrials]
![Covering [implications for] technology](/nks/notes/notes-12-11--covering-implications-for-technology/thumb.png "Covering [implications for] technology")
![[Implications for] chemistry](/nks/notes/notes-12-11--implications-for-chemistry/thumb.png "[Implications for] chemistry")
![Microcosm [and PCE]](/nks/notes/notes-12-12--microcosm-and-pce/thumb.png "Microcosm [and PCE]")
