Theory of Computation

(Up) | See also: Computational Complexity, Automata Theory, Formal Language

---

Works regarding theory of computation, meaning models of computation and the limits they counter. This includes computability theory, including decidable and undecidable problems, also known as the theory of recursive functions. Note that "big" classes such as primitive recursive functions are regarded as complexity topics rather than computability topics here.

Web resources

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound? ★

Other Undecidable Problems (wayback) ★

Scooping the Loop Snooper --- Geoffrey K. Pullum ★

Shtetl-Optimized » Blog Archive » Rosser's Theorem via Turing machines ★

Are there any undecidability results that are not known to have a diagonal argument proof? ★

Is there a finite-dimensional vector space whose dimension cannot be found? ★

Algorithmic Information Theory

The Limits of Reason (Gregory Chaitin) ★

(in Automata Theory) Turing Machines (William Shoaf, 2001, pdf) ★

(in Automata Theory) Csc520 Foundations of Computer Science ★

(in Computational Complexity) Computability and Complexity (Stanford Encyclopedia of Philosophy) ★★★

(in Computational Complexity) Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science ★ 💭

Papers

Unpredictability and Undecidability in Dynamical Systems (online @ gwern.net, scribd.com)

Decidability and Undecidability in Dynamical Systems (online @ inria.hal.science)

(in Category Theory) Physics, Topology, Logic and Computation: A Rosetta Stone (online @ arxiv.org)

Books

Computation: Finite and Infinite Machines (borrow @ archive.org) 🏛️ 💭

The Universal Turing Machine (borrow @ archive.org) ★★★ 💭

Theory of Recursive Functions and Effective Computability (borrow @ archive.org) 💭

Automata and Computability (borrow with print disabilities @ archive.org) ★ 💭

Theory of Computation (borrow with print disabilities @ archive.org, archive.org) 💭

Theories of Computation (borrow with print disabilities @ archive.org) ★ 💭

Computability Theory, Semantics, and Logic Programming (borrow @ archive.org) 💭

Theory of Deductive Systems and its Applications (borrow @ archive.org) ★★★ 💭

Handbook of Theoretical Computer Science (borrow @ archive.org) ★★

(in Formal Language) Introduction to Formal Languages (borrow @ archive.org) (borrow with print disabilities @ archive.org (1991)) ★ 💭

(in Formal Language) Programs, Grammars, Arguments (online @ archive.org)

(in Logic) Mathematical Logic (Kleene) (borrow @ archive.org) 🏛️ 💭