Computation as a Universal and Fundamental Concept
Not long ago, a “computer” was a person who sat at a desk, performing large-scale arithmetic by hand. That version of a computer, bound by human limitations, was still the picture in 1936, when a young mathematician named Alan Turing published a paper now widely regarded as the founding document of computer science, a full decade before anyone built a machine resembling a computer as we know it. Turing proposed what became known as the Turing machine, a concept effectively captured by picturing the human computer at a desk, working along an endless scroll divided into squares, following a short list of rules (an algorithm) to change the symbol in one square before shifting to the next.
Today, computers can chart optimal driving directions across an entire continent, answer nearly any question put to them, hold a fluent conversation, and write working code, all within seconds. These achievements raise a natural question: is there anything computers cannot do?
Professor Tim Roughgarden takes up this question directly in Computation as a Universal and Fundamental Concept, a new five-part series from Ergo. What does it mean to understand computation as a law of nature? How far have we really progressed beyond the concept of a computer proposed ninety years ago by Turing? In an age of quantum computing and generative AI, are we capable of progressing further?
Across the five lectures, Roughgarden illustrates that computer science has always simultaneously pulled in two directions: toward proving what computers can do, and toward proving what they cannot.
One direction is the search for upper bounds, proof that computers can do more than expected. Anatoly Karatsuba disproved his professor’s confident conjecture that the method for multiplication we all learned in grade school could not be improved upon, developing a powerful new algorithm in a single week.
Edsger Dijkstra found the shortcut still running your phone’s driving directions.
George Dantzig built an entire mathematics of optimization, linear programming, to solve a military logistics problem. John von Neumann, shown the result, spotted its hidden connection to game theory.
The other direction is the search for lower bounds, proof that computers cannot do something no matter how the technology improves. This is Turing’s legacy, with the halting problem as the most famous example.
By the early 1970s, the search for upper bounds and the search for lower bounds had converged on the same question: P versus NP. P versus NP asks whether every problem where a proposed solution is easy to check once someone hands it to you is solvable by an algorithmic shortcut.
The stakes are enormous specifically because so many different problems turn out to be, in a precise mathematical sense, the same problem. Sudoku, the Traveling Salesperson Problem, and thousands of others across logistics, scheduling, and biology are all versions of one another: solve any single one of them quickly, and a fast solution to all the rest follows automatically.
Having brought us this far, Roughgarden leaves us with two possible worlds. If P equals NP, all of those thousands of problems fall to fast algorithms at once, and what is possible in science and industry expands overnight. If P does not equal NP, all of them remain permanently out of reach, and the shortcuts that have worked so well elsewhere in computer science simply do not apply here.
Nobody yet knows which world we are in. As we approach quantum computing and develop better AI, Roughgarden again brings us back to Turing and his machine. Some of the boundaries Turing drew in 1936 remain exactly where he left them, untouched by ninety years of progress. Others turn out to be more fragile than expected, at least once quantum mechanics enters the picture. Roughgarden’s series lays out exactly which limits are which, and shows why a technology capable of unsettling one boundary can leave a neighboring one completely intact.
All five lectures can be viewed on Ergo or on YouTube.
Tim Roughgarden is a Professor in the School of Mathematics at the Institute for Advanced Study. He previously spent seven years on the computer science faculty at Columbia and 15 years at Stanford. His main interests are in the connections between computer science and economics, and in the design, analysis, and limits of algorithms.
He is the author of Twenty Lectures on Algorithmic Game Theory, Beyond the Worst-Case Analysis of Algorithms, and the Algorithms Illuminated series, as well as numerous research articles. His work has been recognized with several major awards in theoretical computer science, including the ACM Grace Murray Hopper Award and the Gödel Prize.