Skip to main content

The Halting Problem

Tim Roughgarden

6:41 minute excerpt from the lecture Is There Anything Computers Can't Do?

Professor Tim Roughgarden explains the halting problem, showing why no automated procedure can determine whether a given program will halt or run forever.

Read Transcript › Watch Full Lecture › Watch on YouTube ›

From the Course

Computation as a Universal and Fundamental Concept

Computation as a Universal and Fundamental Concept

Watch Videos

TIM ROUGHGARDEN treats computation as a law of nature, tracing its arc from Turing's proof that some problems are unsolvable to the P versus NP question at the heart of modern computer science.

more excerpts

The Origins of Quantum Mechanics Quantum Computers & The Extended Church-Turing Thesis Algorithmic Shortcuts