Computation as a Universal and Fundamental Concept

Tim Roughgarden begins with a deceptively simple question: is there anything computers cannot do? To answer it, he takes us back to 1936, when Alan Turing, a decade before actual computers existed, laid the foundations of computer science as a byproduct of solving an obscure mathematical problem. Turing's paper introduced the theoretical machine that bears his name and proved something startling: there are problems no algorithm can ever solve, no matter how much time or computing power we throw at them. The halting problem, which asks whether a program will eventually stop running, is forever beyond the reach of any computer.