= Model of computation
A <model of computation> specifies how <input>[inputs] are represented, which <state (computer science)>[states] and operations are available, how execution proceeds and what counts as its <output> and resource cost. Examples include <Turing machine>[Turing machines], random-access machines, <Boolean circuit>[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 <integer>[integers] is one instruction in a unit-cost <abstract machine>[machine] model. In a bit-cost model, operating on arbitrarily long <integer>[integers] requires time depending on their encoded lengths. A bound counting <arithmetic operation>[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 theory>[computability] from the cost of a chosen representation.
Back to article page
