Computability

In math and computer science, researchers have long understood that some questions are fundamentally unanswerable. Now physicists are exploring how even ordinary physical systems put hard limits on what we can predict, even in principle.

By proving a broader version of Hilbert’s famous 10th problem, two groups of mathematicians have expanded the realm of mathematical unknowability.

Researchers got a better look at the thoughts of chatbots, amateurs learned exactly how complicated simple systems can be, and quantum computers passed an essential milestone.

You don’t need 0s and 1s to perform computations, and in some cases it’s better to avoid them.

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

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

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

Mathematical proofs based on a technique called diagonalization can be relentlessly contrarian, but they help reveal the limits of algorithms.

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.