auto
small
medium
large
x-large
Notes
Chapter 12
auto
small
medium
large
x-large
Jump to page
Lookup in index
Search
‹
›
Notes
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