Turing Complete
Turing completeness means a computing system can simulate a Turing machine and compute every computable function — the standard for general-purpose computational power.
Purpose
Judge the computational power ceiling of a language/system and understand the limits of computability.
Mechanism
Requires: conditional branching + arbitrary loops/recursion + read-write memory. Most programming languages are Turing-complete. HTML+CSS (disputed), SQL (recursive CTEs), and regex (backreferences) sit at the edge. The halting problem is undecidable.
Use cases
- Theory of computation
- Language power
- Computability