What's up in

# computability

## Latest Articles

### With Fifth Busy Beaver, Researchers Approach Computation’s Limits

After decades of uncertainty, a motley team of programmers has proved precisely how complicated simple computer programs can get.

### How to Build an Origami Computer

Two mathematicians have shown that origami can, in principle, be used to perform any possible computation.

### An Easy-Sounding Problem Yields Numbers Too Big for Our Universe

Researchers prove that navigating certain systems of vectors is among the most complex computational problems.

### 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.