Turing machine

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.

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.

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

When he invented Turing machines in 1936, Alan Turing also invented modern computing.

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.

The physical nature of computers might reveal deep truths about their uniquely powerful abstract abilities.