Computation and Its Limits

What are computers, at a fundamental level, capable of doing, and what lies beyond their reach? In this introductory lecture, Tim Roughgarden frames computation not as a feature of modern technology, but as a set of deep laws governing the universe itself. He previews a series of questions that have shaped computer science, from Turing's proof that some problems are unsolvable to the enduring mystery of P versus NP. Along the way, he sketches how ideas like universality, reduction, and algorithmic efficiency reveal unexpected connections between seemingly unrelated problems. This episode serves as a guide to the five lectures that follow, offering a map of the concepts, questions, and intellectual stakes of the series.