The Simple Version
A system is Turing complete if it can compute anything that any other computer can compute, given enough time and memory.
The Foundation: What's a Turing Machine?
In 1936, Alan Turing imagined the simplest possible computing device:
- An infinite tape divided into cells (memory)
- A head that can read/write symbols on the tape
- A set of rules (like "if you see a 1, write 0 and move right")
- The ability to move left or right on the tape
That's it. This incredibly simple machine can theoretically compute anything computable.
What Makes Something Turing Complete?
A system is Turing complete if it can simulate a Turing machine. In practice, this means it needs:
- Conditional branching - The ability to do different things based on conditions (if/else)
- Arbitrary memory access - The ability to read and write data
- Looping/recursion - The ability to repeat operations
Why Does It Matter?
If something is Turing complete, it can (in theory) run any program. This is why:
- JavaScript, Python, C, Excel formulas (yes, really), and even PowerPoint are Turing complete
- They can all theoretically compute the same things
- The differences are practical (speed, convenience) not capability
Surprising Turing Complete Things
- Minecraft (with redstone circuits)
- Magic: The Gathering (the card game)
- Excel formulas (with iteration enabled)
- CSS + HTML (controversially, with user interaction)
The Catch: Theoretical vs Practical
"Turing complete" means theoretically capable, not practically useful. You could run a neural network in PowerPoint, but you definitely shouldn't.
It's like saying "a bicycle and a rocket can both get you to California." True, but misses the point.
Simple Analogy for Courtney
"Turing complete means a system has the basic ingredients to do any calculation a computer can do. Like how any kitchen with heat, a knife, and a bowl can theoretically make any dish - even if some kitchens are way more practical for it. Minecraft is technically Turing complete because you can build working computers in it using redstone, even though nobody would actually want to."