Is There Anything Computers Can't Do?

Tim Roughgarden takes us back to the origins of computer science, before computers even existed, to reveal a profound and lasting disappointment at the heart of the discipline. Beginning with Hilbert's ambitious program to put mathematics on solid foundations, Roughgarden traces how Gödel shattered the dream of completeness and how Alan Turing, in his landmark 1936 paper, defined what computation really is through the elegantly simple Turing machine. From there, the lecture builds toward Turing's devastating result: certain problems, including the famous halting problem, are fundamentally unsolvable by any computer, not just today's machines but any machine that could ever be built. Roughgarden walks through the key proof techniques, including the universal Turing machine, diagonalization, and reductions, showing how impossibility spreads across problems. The lecture closes with Church's lambda calculus, the question of whether anything could be more powerful than a Turing machine, and a charming anecdote about the eccentric rituals of mathematical life.