| title | Turing completeness | |||
|---|---|---|---|---|
| date | 2026-03-30 | |||
| captured | 2026-03-30 16:14:43 UTC | |||
| tags |
|
|||
| source | Claude.ai chat | |||
| aliases | ||||
| status | refined |
A system is Turing complete if it can simulate a Turing machine, meaning it can compute anything that is theoretically computable, given enough time and memory. It is the bar for "general-purpose computation."
The concept comes from Alan Turing's 1936 thought experiment: an imaginary machine with an infinite tape (memory cells), a read/write head that moves left or right, and a table of state rules (the "program"). The machine loops: read the current cell, check the rules, write a value, move the head, repeat. Turing proved this absurdly simple setup can solve any problem that any computer can solve.
A system needs all three of these to be Turing complete:
- Conditional branching (if/else, pattern matching)
- Looping or recursion (ability to repeat)
- Arbitrary/unbounded memory (read and write without a fixed limit)
If any one of those is missing, the system can only handle a subset of computable problems.
| Turing complete | NOT Turing complete |
|---|---|
| Python, JavaScript, C, Java | HTML, CSS, JSON, regex |
| Excel (with formulas) | A basic calculator |
| Conway's Game of Life | SQL (without extensions) |
The left column has all three ingredients. The right column is missing at least one (HTML can't loop, a calculator can't branch, pure SQL can't recurse arbitrarily).
Turing completeness says nothing about speed or practicality. You could write an operating system in Conway's Game of Life. You absolutely should not.
It also does not mean infinite power. There are problems (like the halting problem) that no Turing-complete system can solve. Turing complete is the ceiling for computation, and it turns out to be surprisingly easy to reach.
- [[redundant-api-pre-checks-in-wrapper-functions]] - practical API design patterns where understanding computational boundaries (what a library can vs should check) matters