Model of computation

A model of computation is an abstract formal system that specifies how information is represented and how computational steps are performed. Different models clarify what can be computed, how efficiently, and under which assumptions.

Connect

Turing machine: An abstract machine that computes by reading and writing symbols on a tape according to finite rules. It is the canonical model for formalizing algorithms and computability.
Turing machine tape: The potentially unbounded sequence of cells on which a Turing machine reads and writes symbols. It supplies the machine's mutable memory.
Finite automaton: A finite-state machine that recognizes regular languages without unbounded memory. It is strictly less expressive than general-purpose models such as Turing machines.
Automata theory: The study of abstract machines and the formal languages they recognize. It uses finite automata and related models to analyze language recognition.
Thesis of extended Church–Turing: The thesis that efficient physical computation can be simulated efficiently by a probabilistic Turing machine. It asks whether conventional models capture the efficient computations of physical devices.
Lambda calculus: A formal system for function abstraction and application, with computation expressed through expression reduction. It represents computation through function evaluation rather than machine instructions.
Transition function: A rule mapping a machine's current state and input symbol to its next action and state. It specifies the legal computational step in many machine models.
Pushdown automaton: A finite-state machine augmented with a stack, used to recognize context-free languages. Its stack provides more memory than a finite automaton but less than a Turing machine tape.
Algorithm: A finite, specified procedure for solving a problem or performing a computation. Models give algorithms precise representations and operational meanings.
Quantum computational supremacy: A demonstrated task on which a quantum computer substantially outperforms classical computers under specified assumptions. Its claims depend on how classical and quantum computational models are compared.