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
• General Recursive Functions
• Minsky machine
• Fractran
• Rule 110 automaton
• Conway's game of life
• 2-Tag system
• Cyclic Tag
• Tree Rewriting System