What's up in
computability
Latest Articles
Alan Turing and the Power of Negative Thinking
Mathematical proofs based on a technique called diagonalization can be relentlessly contrarian, but they help reveal the limits of algorithms.
Complexity Theory’s 50-Year Journey to the Limits of Knowledge
How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. A string of recent results has started to deliver answers.
The Most Important Machine That Was Never Built
When he invented Turing machines in 1936, Alan Turing also invented modern computing.
How the Slowest Computer Programs Illuminate Math’s Fundamental Limits
The goal of the “busy beaver” game is to find the longest-running computer program. Its pursuit has surprising connections to some of the most profound questions and concepts in mathematics.
Landmark Computer Science Proof Cascades Through Physics and Math
Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics.