Turing completeness is a characteristic of an executor (a set of calculating elements) in computability theory , meaning the ability to implement any computable function on it. In other words, for each computable function there is a calculating element (for example, a Turing machine ) or a program for the executor, and all functions computed by many calculators are computable functions (possibly with some encoding of the input and output data).
The property is named for Alan Turing , who developed an abstract computer - a Turing machine , and which defined many functions that can be calculated by Turing machines.
Examples
Most widely used programming languages are turing-complete. This applies to both imperative languages such as Pascal , and functional ( Haskell ) and logical programming languages ( Prolog ). Some programming languages (Haskell, C ++ ) have turing completeness of compilation time.
Turing-complete normal Markov algorithm , 2-tag system , cellular automaton with rule 110 , inhibitory Petri net , lambda calculus with beta reduction . Turing complete are also unlimited grammars .
Examples of Turing incomplete formalisms are finite automata , primitive recursive functions , context-free and regular grammars.
Universal system
In each Turing-complete class of calculators, there is a universal representative of the class that imitates the execution of an arbitrary given representative of the class. For example, a universal Turing machine along a tape containing the cipher of an arbitrary given Turing machine M and its input chain B imitates the execution of M over B. Currently, universal Turing machines containing less than 23 instructions [1] for combinations of the number of state symbols 4 × 6, 5 × 5. The universal inhibitory Petri net contains 56 vertices [2] .
Notes
Literature
- Brainerd, WS, Landweber, LH Theory of Computation. - Wiley, 1974.