Turing complete

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.

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):

• Turing machines, of course (Alan Turing, 1936)
• Register machines (John von Neumann)
• The lambda calculus (Alonzo Church, 1936)
• Combinator logic (Moses Schönfinkel, 1924)
• Markov algorithms (Andrei Markov, the younger, 1951)
• Semi-Thue Grammars (Axel Thue, Noam Chomsky)
• Post systems (Emil Post, 1943)
• Recursive functions (Stephen Cole Kleene, 1935)
• Insertion-Deletion Systems (Lila Kari et. al., 1996)
• The Game of Life (John Conway) and related one-dimensional cellular automata (Stephen Wolfram)

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.