# Model of computation

models of computationmodelmodels of computingcomputation modelcomputational modelscomputational systemformal modelmachine modelmathematical model of computationmodel computation
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input.wikipedia
100 Related Articles

### Computational complexity theory

computational complexitycomplexity theorycomplexity
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input.
The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage.

### Finite-state machine

finite state machinestate machinefinite automata
A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.

### Computability theory

recursion theorycomputablecomputability
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input.
The use of Turing machines here is not necessary; there are many other models of computation that have the same computing power as Turing machines; for example the μ-recursive functions obtained from primitive recursion and the μ operator.

### Turing machine

deterministic Turing machineTuring machinesuniversal computer
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

### Computer science

computer scientistcomputer sciencescomputer scientists
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input.
In an effort to answer the first question, computability theory examines which computational problems are solvable on various theoretical models of computation.

### Lambda calculus

beta reductionλ-calculusuntyped lambda calculus
It is a universal model of computation that can be used to simulate any Turing machine.

### Computational complexity

complexitycomputational burdenamount of computation
The computational complexity of an algorithm can be measured given a model of computation.
The evaluation of the complexity relies on the choice of a model of computation, which consists in defining the basic operations that are done in a unit of time.

### Kahn process networks

Kahn process network
Kahn process networks (KPNs, or process networks) is a distributed model of computation where a group of deterministic sequential processes are communicating through unbounded FIFO channels.

### Interaction nets

Interaction nets are a graphical model of computation devised by Yves Lafont in 1990 as a generalisation of the proof structures of linear logic.

### Function (mathematics)

functionfunctionsmathematical function
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input.
For giving a precise meaning to this concept, and to the related concept of algorithm, several models of computation have been introduced, the old ones being general recursive functions, lambda calculus and Turing machine.

### Analysis of algorithms

computational complexitycomplexity analysiscomputationally expensive
In the field of runtime analysis of algorithms, it is common to specify a computational model in terms of primitive operations allowed which have unit cost, or simply unit-cost operations.
Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called model of computation.

### Decision tree model

algebraic decision treequery complexitydecision tree complexity
In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of branching operations based on comparisons of some quantities, the comparisons being assigned unit computational cost.

### Algorithm

algorithmsalgorithm designcomputer algorithm
The computational complexity of an algorithm can be measured given a model of computation.

### Implementation

implementedimplementimplementing
Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.

### Μ-recursive function

partial recursive functionrecursive function theorygeneral recursive function

### Combinatory logic

combinatorcombinator calculuscombinators

### Abstract rewriting system

abstract rewritingReduction relationabstract rewriting systems

### Cellular automaton

cellular automataCACell games (cellular automaton)

### Petri net

Petri netsPetri net theoryconcurrent systems

### Random-access machine

random access machineRAM machineRAM machine model
A commonly used example is the random access machine, which has unit cost for read and write access to all of its memory cells.

### Model-driven engineering

Model Driven Engineeringmodel-driven developmentmodel-driven software development
In model-driven engineering, the model of computation explains how the behaviour of the whole system is the result of the behaviour of each of its components.

### Abstract machine

abstract computerabstract computer modelcomputational models

### Stack machine

stack architecturestack-basedpush down stack