The end of 2024 seems a particularly uncertain time in history, and theoretical computer science is no exception. Amid several breakthroughs and new findings, the field also confronted its own doubts and limitations.
For example, artificial intelligence once again dominated the popular discourse this year. Researchers have begun to understand what might be going on within the “black boxes” of neural networks that power chatbots such as Bard and ChatGPT, and to show that these systems truly understand the data they’re manipulating and composing. But there’s also a growing sense that AI’s progress has already started to slow.
Other areas of computer science saw clearer successes. After decades of hiding, an elusive numerical critter known as the fifth busy beaver finally gave itself up. But even here the news is not all good: Initial searches for its successor — the sixth busy beaver — suggest that it may lie beyond impassable mathematical barriers.
The field of error-correcting codes — mathematical constructions that can fix themselves if an error has occurred — also rose in prominence in 2024. Researchers showed, for the first time, that an error-correcting technique essential for quantum computers really does work. But another finding showed that classical error-correcting codes are fundamentally inefficient, dashing hopes for practical versions of this “magical phenomenon.”
Kristina Armitage/Quanta Magazine
Big Beaver Breakthroughs
This summer, a team of enthusiastic amateurs solved one of the biggest open questions in computer science when they found the fifth busy beaver. Named for a particularly industrious kind of computer program that takes a long time to run, the problem is connected to some of the deepest open questions in computer science and mathematics.
The problem involves Turing machines, some of the simplest possible computing devices, first conceived by Alan Turing as a model for a general computer and now easily simulated online. Depending on their initial settings, these can either run forever or halt after a set number of steps. The busy beaver problem asks: Given only a certain number of rules governing the machine, how long can it run, short of forever? Researchers solved this problem for machines with 1, 2, 3 or 4 rules (1, 6, 21 and 107 steps, respectively), but the fifth busy beaver number eluded them for decades.
Quanta staff writer Ben Brubaker chronicled the efforts of a global team, made up mostly of nonexperts, to find the number — it’s 47,176,870 — and prove that it couldn’t be higher. The problem doesn’t have any direct applications, but finding the solution does represent a kind of victory over overwhelming mathematical complexity — one that early searches for the sixth busy beaver suggest we may never see again.
And in January, we wrote about another diverse team of nonprofessionals who helped solve a different kind of numerical puzzle. This effort focused on the Game of Life, by John Conway, and the hunt for repeating patterns of specific lengths. By finding patterns that repeated after 19 and 41 steps, they proved that the Game of Life is “omniperiodic” — capable of repeating after every possible number of steps.
Better Living Through Codes
Quantum computers have long tantalized researchers, but despite years of work, a truly useful one remains far out of reach. This is partly due to their nature: Quantum computers exploit the vagaries of quantum mechanics, the rules governing the universe’s most minute interactions, and this makes them vulnerable to significant errors. Almost 30 years ago, researchers showed that it’s possible to combine qubits — the quantum equivalent of a computer’s bits — in such a way that they could tolerate errors. But for this to work, each individual qubit’s error rate must be below a certain minimum threshold. In December, a team at Google announced that they’d reached that level, showing for the first time that quantum error-correction codes can make these exotic machines possible (although still not anytime soon).
Quanta also covered another new kind of quantum error-correcting code in February, this one built out of aperiodic tilings — sets of shapes that combine in ways that never repeat. As Brubaker wrote, the connection is possible because for both the tiles and the codes, “learning about a small part of a large system reveals nothing about the system as a whole.”
Quantum error correction didn’t have all the fun this year — scientists also answered a major question about classical error-correcting codes that can be used in the computers we all employ today. The only known working examples have always been extremely inefficient, and researchers have wondered if it might be possible to do better. After more than 20 years, the answer, at least for certain simple approaches, is no: There’s simply no way around that inefficiency.
Kristina Armitage/Quanta Magazine
Peering Within the Quantum
Many of the biggest discoveries this year showed that, through the lens of computer science, even the inscrutable world of quantum mechanics can become slightly clearer. Tiny particles interact in complicated ways, and it’s still difficult for scientists to fully understand a given system of them. But four computer scientists recently developed a new algorithm that can efficiently spit out a full description of any system, a first for the field. By combining an optimization tool from mathematics with a computer science approach known as a relaxation technique, the team showed how to quickly generate any quantum system’s Hamiltonian — a kind of super equation that fully describes it — so long as it is at a constant temperature.
The same team of researchers ended up making another big quantum discovery when they proved that rising temperatures don’t just weaken the interactions between particles known as entanglement: There’s always a specific temperature at which entanglement vanishes completely.
A separate team also showed that a problem related to such quantum systems — finding their local minimum energy level — can be relatively easy for a quantum computer to do. Not only is this welcome progress in the field of quantum physics, but it also proves that there really might be useful problems quantum computers can solve that are beyond the reach of classical machines. And quantum theory’s complexities could also provide a new basis for cryptography, should current cryptography crumble under qubits.
Myriam Wares for Quanta Magazine
A Growing Understanding of AI
Artificial intelligence is perhaps the most visible — and most misunderstood — area of theoretical computer science. This year OpenAI, of ChatGPT fame, released its o1 chatbot models, which seem to be capable of surprising and powerful new feats of ingenuity. But despite such progress, the inner workings of these tools remains unclear, leaving room for security breaches and other shenanigans.
Researchers are particularly curious about whether these models truly understand what they’re saying or if they’re just “stochastic parrots,” in the words of a 2021 review paper, simply repeating variations of what they’ve heard before. New research suggests that these machines might really understand. When a team at Google DeepMind studied the skills necessary for these language models to pull off their extraordinary feats, they concluded that the machines can’t be simply regurgitating training data. “They demonstrate convincingly that [certain models] can generate text that combines skills and topics in ways that almost certainly did not occur in the training data,” said the AI pioneer Geoff Hinton, who won the 2024 Nobel Prize in Physics for his work with machine learning.
Indeed, a phenomenon known as grokking, in which models are overtrained to the point of unexpected mastery, suggests new ways to understand how these mysterious machines process information. Other teams are using the techniques of computational complexity — a branch of computer science that studies the relative difficulty of different problems — to help explain why language models seem to do so much better when they solve problems step by step.
