Computability
/kəmˌpjuː.təˈbɪl.ɪ.ti/ · Noun · Development · Origin: 1936
Definitions
The study of which problems can be solved by algorithms at all, regardless of time or space. The halting problem — determining whether an arbitrary program eventually stops — is the canonical example of an uncomputeable problem.
In plain English: The question of what computers can and can't do in principle — not how fast, but whether it's possible at all.
Example: "Before optimizing, ask if the problem is even computable. You can't write a perfect virus scanner — that's reducible to the halting problem."
Origin Story
The branch of math that proved some problems can never be solved
**Computability theory** (originally called recursion theory) began with Kurt Godel's incompleteness theorems (1931), which shattered the dream that mathematics could be fully mechanized. Turing's 1936 paper then showed specific problems that no algorithm can solve.
The most famous unsolvable problem is the **halting problem**: no program can determine, in general, whether another program will eventually stop or run forever. Turing proved this by contradiction -- assuming such a program exists leads to a paradox.
Computability theory establishes the absolute limits of what computers can do. These limits aren't about speed or memory -- they're fundamental. No future technology, no matter how advanced, will solve the halting problem. It's not an engineering limitation; it's a mathematical impossibility.
Coined by: Kurt Godel (incompleteness), Alan Turing (halting problem), Alonzo Church
Context: 1931 (Godel), 1936 (Turing, Church)
Fun fact: The halting problem has practical consequences: it means no compiler can perfectly detect all infinite loops, no antivirus can catch all malware, and no type system can prevent all bugs. Rice's theorem generalizes this: ANY non-trivial property of programs is undecidable.