Chapter 12 Notes > Section 8

	Notes for 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 in Mathematica 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 PAGE IMAGES RELATED LINKS Main text from section Downloadable programs for this section Downloadable images Search Forum for this section Post a comment NKS | Online FAQs

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