Theory of Computation

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

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)

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 @ archive.org)

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

Theories of Computation (borrow @ archive.org)

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

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