Turing-complete languages or machines are those that can express arbitrary computations, that is, they can emulate arbitrary Turing machines.

This is not at all the same as the capability to solve any mathematical problem: many perfectly defined mathematical problems are provably unsolvable.

As a matter of fact, the Turing machine was invented to prove this.

A simple Turing-complete formalism is, obviously, the Turing machine; another, the lambda calculus; another is the arbitrary rewrite grammar often used as the last formalism in the Chomsky hierarchy.

Very small subsets of most programming languages are already Turing-complete, on the condition that they can access arbitrary amounts of memory. C, for instance, isn't, because it must address all memory with pointers of a fixed size; but a variant that uses pointers of arbitrary size would be trivial to define.

A programming language (alternatively, a computational model) is called Turing complete if it is equivalent to the Turing machine model: any program written in the language can be simulated with some Turing machine, and every Turing machine can be simulated by some program written in the language.

The Church-Turing thesis states that any "interesting" computational model is Turing complete.

Since the (technical) theory of recursive functions is Turing complete, a programming language is Turing complete iff every program calculates some recursive function, and every recursive function may be calculated by some program in the language.

Primitive recursive functions are not Turing complete: they cannot express the Ackermann function. C and Pascal are Turing complete if we're careful to ignore some details (e.g. a C implementation must use pointers of some finite size sizeof(void *), implying it can only use some finite amount of data). Real programming languages are Turing complete only if we ignore the constraints of finiteness.

Examples of Turing complete formal systems include the following (along with the person credited for inventing the system, and date of seminal paper describing it, where applicable, or known):

That is, it is possible for any instances of these systems to simulate and be simulated by any of the others. The fact that all of these formal systems for computation can generate only recursively enumerable languages and calculate partial recursive functions lends credence to the Church-Turing Thesis.

These various Turing complete formal systems have become the basis for various styles of programming and associated programming languages. For instance the register machine model has become the main model behind which nearly all machine languages for nearly all modern microprocessors are based. The lambda calculus is the basis for all functional languages, and the related combinator logic is used for some implementations.

Log in or register to write something here or to contact authors.