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