A system is Turing complete iff it can simulate any Turing machine.
Any 2 Turing-complete systems can simulate each other. They are computationally equivalent.
Minimum Requirements
A system is Turing complete iff it has:
- Unbounded memory (no fixed storage limit)
- Conditional branching
- Loops or recursion
Significance
A Turing-complete system can compute any Turing-computable function. No real computer exceeds the computational power of a Turing machine (ignoring memory and time limits).
Turing Tarpit
A Turing-complete system that is deliberately minimal or impractical to program in.
Examples:
- Brainfuck (only 8 instructions)
- Malbolge
Examples
Systems known to be Turing complete:
- Most general-purpose programming languages (C, Python, Java)
- Lambda calculus
- Conway’s Game of Life (cellular automaton)
- SQL with recursive CTEs
- Rule 110 elementary cellular automaton