Turing Completeness

Definitions

1. The property of a computational system that can simulate any Turing machine — meaning it can compute anything that is computable, given enough time and memory. Most programming languages are Turing complete. Accidentally Turing-complete systems include CSS+HTML, Magic: The Gathering, and PowerPoint.

   In plain English: A system that can theoretically compute anything any computer can compute, even if impractically.

   Example: "Yes, SQL is Turing complete with recursive CTEs — but please don't write a raytracer in it."

Etymology

1936

Alan Turing published 'On Computable Numbers,' introducing the Turing machine as a model of computation.

1950s

The term 'Turing complete' emerged to classify systems with equivalent computational power to a Turing machine.

Related Terms

• Turing machine
• Halting Problem
• Lambda Calculus
• Boolean Algebra
• Shannon Entropy
• NP-Completeness
• Finite State Machine
• Church-Turing Thesis
• Graph Theory
• Floating Point