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 have 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

• Multi-tape
• Multi-headed
• Reversible
• Turmite
• Multi-dimensional tape
• Branching tape
• Uniform-action
• Semi-infinite tape

Lambda calculus

• SK Calculus
• SKI Calculus
• BCKW Calculus
• Iota
• Jot

Brainfuck

• Boolfuck
• Bitter
• Smallfuck
• BitChanger

Cellular automata

• Rule 110 automaton
• Conway's game of life
• Doodle automaton
• Pebble automaton

Tag systems

• 2-Tag system
• Cyclic tag system
• Tree Rewriting System
• String rewriting system

Counter machines

• Minsky machine

• CounterScript

Other

• General Recursive Functions
• Fractran
• Wang tiles
• Diophantine equations
• Piecewise affine function

See Also

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