Turing completeness

A Turing-complete system is a system that can compute every computable function. A Turing-complete system can be used to simulate any Turing machine or other Turing-complete systems.

The halting problem is uncomputable on any Turing-complete system.

To be Turing-complete, a system must be able to store unbounded memory and having access to the memory. There must be also infinitely many different non-halting programs (like "while" loops or recursion).

List of Turing-complete systems

This list is non-exhaustive.

• Turing machine
• Lambda calculus
• SK calculus
• General Recursive Functions
• Minsky machine
• Fractran
• Rule 110 automaton
• Conway's game of life
• 2-Tag system
• Cyclic Tag
• Tree Rewriting System
• Brainfuck

See Also

Wikipedia article about computability: https://en.wikipedia.org/wiki/Computability