How do we rigorously study computation without being tied to specific hardware implementations?
A model of computation is a mathematical abstraction of a computer used to formally analyze what problems can be solved and how efficiently.
Computer scientists work with various models:
- Turing machine - most commonly examined, simple to formulate and analyze
- Lambda calculus - function-based computation
- Register machine - idealized computer with numbered registers
- μ-recursive functions - mathematical function definition
The Turing machine is preferred because it is simple to formulate, can be analyzed to prove results, and represents what many consider the most powerful “reasonable” model of computation (Church-Turing thesis).
- Mathematical abstraction of computers
- Used to prove results about computability and complexity
- Different models have different capabilities but are often equivalent
- Enables rigorous analysis without hardware dependencies
- Built from: Turing Machine, Lambda Calculus, Register Machine
- Builds into: Computability Theory, Computational Complexity Theory
- Related: Theory of Computation, Algorithm
- All reasonable models of computation are equivalent (Church-Turing thesis)
- The infinite memory of Turing machines is idealized—any decidable problem needs only finite memory