A model of computation specifies how inputs are represented, which states and operations are available, how execution proceeds and what counts as its output and resource cost. Examples include Turing machines, random-access machines, Boolean circuits and the lambda calculus. A mathematical algorithmic claim is interpreted within such a model, even when the model is left implicit.
For example, adding two integers is one instruction in a unit-cost machine model. In a bit-cost model, operating on arbitrarily long integers requires time depending on their encoded lengths. A bound counting arithmetic operations therefore need not be a bound on bit complexity. Likewise, a circuit family can supply separate hardware for each input length, while a uniformity requirement asks one algorithm to generate those circuits. Stating the model makes efficiency comparisons meaningful and separates questions of computability from the cost of a chosen representation.
Articles by others on the same topic
A model of computation is a formal framework that describes how computations are performed. It outlines the rules and mechanisms by which processes or algorithms can be executed, providing a systematic way to study and analyze computational problems and their complexities. Different models of computation allow us to understand various computational paradigms and their capabilities and limitations.