Theory of computation

Theory of computation studies which problems can be solved by formal computational models, how much time and memory solutions require, and where computation has limits.

Turing machine: An abstract machine that computes by changing symbols on an unbounded tape according to finite rules. It provides a standard model for defining algorithms and computability.
Church–Turing thesis: The claim that every effectively calculable function can be computed by a Turing machine. It links the mathematical machine model to the informal idea of an algorithm.
P versus NP problem: The open question of whether every problem whose solution can be checked quickly can also be solved quickly. It asks whether efficient verification implies efficient solution across a central class of problems.
Halting problem: The problem of deciding whether an arbitrary program eventually stops on a given input. Its undecidability demonstrates that some well-defined computational questions have no general algorithm.
Finite-state machine: A computational model with finitely many states and transitions, often used to recognize regular patterns. It captures a restricted form of computation central to automata theory.
Universal Turing machine: A Turing machine that simulates any other Turing machine when given its description and input. It explains how one general-purpose machine can execute encoded programs.
NP-completeness: A classification of decision problems in NP to which every problem in NP can be reduced efficiently. It identifies problems whose efficient solution would yield efficient solutions for all NP problems.
Decidable problem: A decision problem for which an algorithm always halts and returns the correct yes-or-no answer. It contrasts with undecidable problems, which no algorithm solves on every input.
Formal language: A set of finite strings over an alphabet, specified by rules or a recognition procedure. Computational models are often compared by the languages they recognize.
Big O notation: A notation that describes an upper bound on how a function grows asymptotically. It expresses how algorithmic resource use scales as input size increases.

Linked from 1 page

Blum's speedup theoremNarrower topic: The theorem belongs to the foundational mathematical study of programs and resources.