Editing Theory of computation (section)

== Models of computation ==<!-- This section is linked from [[Abstract machine]] -->
{{main|Model of computation}}

Aside from a [[Turing machine]], other equivalent (see [[Church–Turing thesis]]) models of computation are in use.

;[[Lambda calculus]]: A computation consists of an initial lambda expression (or two if you want to separate the function and its input) plus a finite sequence of lambda terms, each deduced from the preceding term by one application of [[Beta reduction]].
;[[Combinatory logic]]
:is a concept which has many similarities to <math>\lambda</math>-calculus, but also important differences exist (e.g. fixed point combinator '''Y''' has normal form in combinatory logic but not in <math>\lambda</math>-calculus). Combinatory logic was developed with great ambitions: understanding the nature of paradoxes, making foundations of mathematics more economic (conceptually), eliminating the notion of variables (thus clarifying their role in mathematics).
;[[μ-recursive function]]s: a computation consists of a mu-recursive function, ''i.e.'' its defining sequence, any input value(s) and a sequence of recursive functions appearing in the defining sequence with inputs and outputs.  Thus, if in the defining sequence of a recursive function <math>f(x)</math> the functions <math>g(x)</math> and <math>h(x,y)</math> appear, then terms of the form 'g(5)=7' or 'h(3,2)=10' might appear.  Each entry in this sequence needs to be an application of a basic function or follow from the entries above by using [[Function composition (computer science)|composition]], [[primitive recursion]] or [[μ-recursive function|μ recursion]].  For instance if <math>f(x)=h(x,g(x))</math>, then for 'f(5)=3' to appear, terms like 'g(5)=6' and 'h(5,6)=3' must occur above.  The computation terminates only if the final term gives the value of the recursive function applied to the inputs.
;[[Markov algorithm]]: a [[string rewriting system]] that uses [[grammar]]-like rules to operate on [[string (computer science)|strings]] of symbols.
;[[Register machine]]
:is a theoretically interesting idealization of a computer. There are several variants. In most of them, each register can hold a natural number (of unlimited size), and the instructions are simple (and few in number), e.g. only decrementation (combined with conditional jump) and incrementation exist (and halting). The lack of the infinite (or dynamically growing) external store (seen at Turing machines) can be understood by replacing its role with [[Gödel numbering]] techniques: the fact that each register holds a natural number allows the possibility of representing a complicated thing (e.g. a sequence, or a matrix etc.) by an appropriately huge natural number — unambiguity of both representation and interpretation can be established by [[number theory|number theoretical]]  foundations of these techniques.

In addition to the general computational models, some simpler computational models are useful for special, restricted applications.  [[Regular expressions]], for example,  specify string patterns in many contexts, from office productivity software to [[programming language]]s. Another formalism mathematically equivalent to regular expressions, [[finite automata]] are used in circuit design and in some kinds of problem-solving. [[Context-free grammar]]s  specify programming language syntax.  Non-deterministic [[pushdown automaton|pushdown automata]] are another formalism equivalent to context-free grammars. [[Primitive recursive function]]s are a defined subclass of the recursive functions.

Different models of computation have the ability to do different tasks. One way to measure the power of a computational model is to study the class of [[formal language]]s that the model can generate; in such a way to the [[Chomsky hierarchy]] of languages is obtained.