Model of computation

<h2 id="categories">Categories</h2>
<p>Models of computation can be classified into three categories: sequential models, functional models, and concurrent models.
</p>
<h3>Sequential models</h3>
<p>Sequential models include:
</p>
<ul><li><a href="/facts/Finite-state_machine/GMusWd0a">Finite-state machines</a></li>
<li>Post machines (<a href="/facts/Post%25E2%2580%2593Turing_machine/neqsP142">Post–Turing machines</a> and <a href="/facts/Tag_system/VMxTCpop">tag machines</a>).</li>
<li><a href="/facts/Pushdown_automata/kEPRC70F">Pushdown automata</a></li>
<li><a href="/facts/Register_machine/2SCc9Xof">Register machines</a>
<ul><li><a href="/facts/Random-access_machine/9NrNtVSd">Random-access machines</a></li></ul></li>
<li><a href="/facts/Turing_machine/ojCtglYu">Turing machines</a></li>
<li><a href="/facts/Decision_tree_model/FalJqMSd">Decision tree model</a></li>
<li><a href="/facts/External_memory_model/sCcj8M8o">External memory model</a></li></ul>
<h3>Functional models</h3>
<p>Functional models include:
</p>
<ul><li><a href="/facts/Abstract_rewriting_system/FNIYHu2k">Abstract rewriting systems</a></li>
<li><a href="/facts/Combinatory_logic/D7NNo4xT">Combinatory logic</a></li>
<li><a href="/facts/General_recursive_function/pQezUupS">General recursive functions</a></li>
<li><a href="/facts/Lambda_calculus/DaD3RuQ4">Lambda calculus</a></li></ul>
<h3>Concurrent models</h3>
<p>Concurrent models include:
</p>
<ul><li><a href="/facts/Actor_model/MJ49opnU">Actor model</a></li>
<li><a href="/facts/Cellular_automaton/6gfkjKAW">Cellular automaton</a></li>
<li><a href="/facts/Interaction_nets/hdc9aAbT">Interaction nets</a></li>
<li><a href="/facts/Kahn_process_networks/LQcsRIrA">Kahn process networks</a></li>
<li><a href="/facts/Logic_gate/RHLulvKI">Logic gates</a> and <a href="/facts/Circuit_(computer_science)/vWgfC29C">digital circuits</a></li>
<li><a href="/facts/Petri_nets/BK7eTHNm">Petri nets</a></li>
<li><a href="/facts/Process_calculus/RmAEJ2tN">Process calculus</a></li>
<li><a href="/facts/Synchronous_Data_Flow/pV0kgX8B">Synchronous Data Flow</a></li></ul>
<p>Some of these models have both <a href="/facts/Deterministic_model/oT1NvyHD">deterministic</a> and  <a href="/facts/Nondeterministic_model_of_computation/zv2x6XPG">nondeterministic</a> variants. Nondeterministic models  correspond to limits of certain sequences of finite computers, but do not correspond to any subset of finite computers; they are used in the study of <a href="/facts/Computational_complexity/Qenh22Ja">computational complexity</a> of algorithms.
</p><p>Models differ in their expressive power; for example, each function that can be computed by a <i>finite-state machine</i> can also be computed by a <i>Turing machine</i>, but not vice versa.
</p>
<h2 id="uses">Uses</h2>
<p>In the field of runtime <a href="/facts/Analysis_of_algorithms/pStoBgBn">analysis of algorithms</a>, it is common to specify a  computational model in terms of <i>primitive operations</i> allowed which have unit cost, or simply unit-cost operations. A commonly used example is the <a href="/facts/Random-access_machine/9NrNtVSd">random-access machine</a>, which has unit cost for read and write access to all of its memory cells. In this respect, it differs from the above-mentioned Turing machine model.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Stack_machine/IBtk4NRA">Stack machine</a> (0-operand machine)</li>
<li><a href="/facts/Accumulator_machine/gH4V0l76">Accumulator machine</a> (1-operand machine)</li>
<li><a href="/facts/Register_machine/2SCc9Xof">Register machine</a> (2,3,... operand machine)</li>
<li><a href="/facts/Random-access_machine/9NrNtVSd">Random-access machine</a></li>
<li><a href="/facts/Abstract_machine/zuC4RKLn">Abstract machine</a></li>
<li><a href="/facts/Cell-probe_model/qaFmxzeA">Cell-probe model</a></li>
<li><a href="/facts/Robertson%25E2%2580%2593Webb_query_model/6b3fS9GN">Robertson–Webb query model</a></li>
<li><a href="/facts/Chomsky_hierarchy/tUYCL00R">Chomsky hierarchy</a></li>
<li><a href="/facts/Turing_completeness/73goop44">Turing completeness</a></li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li>Fernández, Maribel (2009). <i>Models of Computation: An Introduction to Computability Theory</i>. Undergraduate Topics in Computer Science. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-84882-433-1.</li>
<li><a href="/facts/John_E._Savage/UcJL6V5j">Savage, John E.</a> (1998). <i>Models Of Computation: Exploring the Power of Computing</i>. Addison-Wesley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0201895391.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>"Models of Computation" (PDF). <a href="https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.pdf" target="_blank">https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Model of computation open-in-new

Model of computation