Moravec's Paradox
A computer beat the world chess champion in 1997. Getting one to pick up a cup it has not seen before is still hard.
198811 min read
Type
Computation
What algorithms and machines can and cannot do.
10 entriesFilter these further →
Intermediate
Curious teenagers and general adult readers.
The Two Generals' Problem
Two armies must attack at the same moment. Any message can be lost, including the one confirming the last one arrived.
1975 (proved), 1978 (named)18 min read
Advanced
Undergraduate level in the relevant field.
Maxwell's Demon
A tiny creature sorting fast molecules from slow ones appears to make heat flow the wrong way, for free, forever.
1867 (letter to Tait), 1871 (published in Theory of Heat)18 min read
The Halting Problem
No program can ever be written that reliably tells you whether another program will finish running. This is not a limit of our cleverness.
193620 min read
The Byzantine Generals Problem
Several generals must attack together or be destroyed. They can only send messengers, and some of the generals are traitors.
198222 min read
The CAP Theorem
A system spread across several machines can give you consistent answers, or always answer at all. The network makes you choose.
2000 (conjectured), 2002 (proved)23 min read
Berry's Paradox
"The smallest number that cannot be described in fewer than twelve words." That description is eleven words long.
1906 (published by Russell, crediting Berry); communicated c. 190419 min read
Levinthal's Paradox
A protein has more possible shapes than the universe has atoms, yet it finds the right one in less than a thousandth of a second.
1968–196917 min read
Expert
Graduate level or specialist readers.
Gödel's Incompleteness Theorems
In any system of arithmetic strong enough to be useful, there are true statements it can never prove. Including this one.
193125 min read
The FLP Impossibility Result
A handful of computers cannot be guaranteed to agree on a single value if even one of them might be slow. Not merely hard — impossible.
198523 min read