Theory of Computation

Theory of Computation addresses models of computation, decidability, and turing machines. It sits within Theoretical Foundations and inherits that area’s core questions about correctness, scale, and tractability. This page surveys the conceptual axes of the topic and points to the references that frame ongoing research and teaching. The intent is to be useful both as an entry point for newcomers and as an index for practitioners cross-checking their mental model against the field’s primary sources.

Work on theory of computation can be organised around a few interlocking concerns: the formal objects under study, the algorithms or systems that compute over them, the resource trade-offs (time, memory, communication, statistical efficiency), and the empirical or theoretical guarantees that practitioners rely on. The sources cited below approach the topic from a mix of these angles.

Foundational references

Sipser, Introduction to the Theory of Computation (2012) is a standard reference for this material and is used both as a curriculum anchor and as a long-form survey of techniques. Hopcroft, Introduction to Automata Theory, Languages, and Computation (2006) is a standard reference for this material and is used both as a curriculum anchor and as a long-form survey of techniques.

Historical context

On Computable Numbers, with an Application to the Entscheidungsproblem (Turing, 1936) situates the topic in its historical trajectory; revisiting it clarifies which ideas in current practice are recent and which trace back to the field’s founding texts.

Open methodological questions in theory of computation cluster around how to compose the techniques above under realistic constraints — scale, adversarial inputs, partial observability, and shifting workloads. The cited references give the precise statements, proofs, and empirical evaluations that this overview only sketches; downstream topic pages drill into specific subfields.