Chapter 12: The Principle of Computational Equivalence

Section 1: Basic Framework

All is computation

Section 2: Outline of the Principle

Note for mathematicians [about PCE] History [of PCE] [History of] Church's Thesis

Section 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] Encodings [for universality] Density of universal systems Proving universality History [of universal objects] [Construction of] universal objects Block occurrences [in rule 30]

Section 4: The Validity of the Principle

Continuum and cardinality Computable reals Diagonal arguments Continuous computation Initial conditions [and continuity] Constructible reals [Universality in] equations [Time compression in] ODEs Emulating discrete systems [with continuous ones] Time and gravity Human thinking [and PCE] Intermediate degrees

Section 5: Explaining the Phenomenon of Complexity

Definition of complexity Ingredients for complexity Relativism and equivalence

Section 6: Computational Irreducibility

History [of computational irreducibility] [History of] exact solutions Amount of computation [and computational irreducibility] More complicated rules [and reducibility] [Examples of] reducible systems Speed-up theorems [Computation of] mathematical functions Formulas [and computational irreducibility] [Examples of] short computations Intrinsic limits in science

Section 7: The Phenomenon of Free Will

History [of ideas about free will] Determinism in brains Amounts of free will Responsibility [and free will] [Free] will and purpose Source of [free] will

Section 8: Undecidability and Intractability

History [of undecidability] Mathematical impossibilities Code 1004600 Halting problems Proofs of undecidability Examples of undecidability Undecidability in cellular automata [Undecidability in] natural systems Undecidability and sets Undecidability in tiling problems Correspondence systems Multiway tag systems Word problems Sequence equations [Classes of] fast algorithms Sorting networks Computational complexity theory History [of computational complexity theory] Lower bounds [on computational complexity] Algorithmic complexity theory [One-sided] Turing machines Functions [computed by Turing machines] [Turing] machine 1507 Properties [of example Turing machines] Longest halting times [in Turing machines] Growth rates [of halting times] [Turing] machine 600720 NP completeness [NP completeness in] natural systems P versus NP questions Non-deterministic Turing machines Implementation [of TM cellular automaton] Satisfiability [emulating Turing machines] Density of difficult problems Rule 30 inversion [Intractability in] systems of limited size Quantum computers Circuit complexity [Computational complexity of] finding outcomes P completeness

Section 9: Implications for Mathematics and Its Foundations

History [of concept of mathematics] [History of] models of mathematics Axiom systems Basic logic [and axioms] Predicate logic [Axioms for] arithmetic Algebraic axioms Groups [and axioms] Semigroups [and axioms] Fields [and axioms] Rings [and axioms] Other algebraic systems Real algebra [and axioms] [Axioms for] geometry Category theory Set theory [and axioms] General topology [and axioms] [Axioms for] real analysis Axiom systems for programs Implementation [of proof example] Proof structures Substitution strategies [in proofs] One-way transformations [as axioms] Axiom schemas Reducing axiom [system] details [Mathematical] proofs in practice Properties [of example multiway systems] Nand tautologies [Methods for] proof searching Automated theorem proving Truth and falsity [in formal systems] Gödel's Theorem Properties [of example multiway systems] Essential incompleteness [in axiom systems] [Universality of] predicate logic [Universality of] algebraic axioms [Universality of] set theory Universal Diophantine equation Hilbert's Tenth Problem Polynomial value sets Statements in Peano arithmetic Transfinite numbers Growth rates [of functions] [Examples of] unprovable statements Encodings of arithmetic [by different operations] [The concept of] infinity Diophantine equations Properties [of Diophantine equations] Large solutions [to Diophantine equations] Nearby powers [and integer equations] Unsolved problems [in number theory] Fermat's Last Theorem More powerful axioms [for mathematics] Higher-order logics Truth and incompleteness Generalization in mathematics Cellular automaton axioms [Theorems about] practical programs Rules [for multiway systems examples] Consistency [in axiom systems] Properties [of example multiway systems] Non-standard arithmetic [Unprovable statements in] reduced arithmetic Generators and relations [and axiom systems] Comparison to multiway systems Operator systems [History of] truth tables Proofs of axiom systems Junctional calculus Equivalential calculus Implicational calculus Operators on sets 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] Model theory Pure equational logic Multiway systems [and operator systems] Logic in languages Properties [of logical primitives] Notations [for logical primitives] Universal logical functions Searching for logic [axioms] Two-operator logic [axioms] History [of logic axioms] Theorem distributions [in standard mathematics] Multivalued logic Proof lengths in logic Nand theorems Finite axiomatizability Empirical metamathematics Speedups in other systems Character of mathematics Invention versus discovery in mathematics Ordering of [mathematical] constructs Mathematics and the brain Frameworks [in mathematics]

Section 10: Intelligence in the Universe

Animism The weather Defining intelligence Mimesis Defining life Origin of life Self-reproduction Extraterrestrial life Forms of living systems History [of extraterrestrial life] Bird songs Whale songs Animal communication Theories of communication Mathematical notation Computer communication [Ideas of] meaning in programs Meaning and regularity Forms of [engineered] artifacts Recognizing artifacts Artifacts in data Animal artifacts [Meaning in] molecular biology Messages in DNA Decompilers Complexity and theology Purpose in archeology Dead languages Teleology Possible purposes [for systems] Purposeful computation 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] Minimal theories Earth from space Astronomical objects Natural radio emissions Artificial radio signals [History of] SETI Detection methods [for SETI] Higher perception and analysis Messages to send [to extraterrestrials] P versus NP [and messages] Science fiction [and extraterrestrials] Practical arguments [about exterrestrials] Physics as intelligence

Section 11: Implications for Technology

Covering [implications for] technology Applications of randomness Self-assembly Nanotechnology Searching for technology Methodology in this book [Implications for] chemistry Interesting chemicals Alkane properties Components for technology Future technology

Section 12: Historical Perspectives

Human uniqueness Animism Universe as intelligent Non-Western thinking Aphorisms Postmodernism Microcosm [and PCE] Human future Philosophical implications

From Stephen Wolfram: A New Kind of Science [citation]