The video loads from YouTube only after you press Play.

Proof That Computers Can't Do Everything (The Halting Problem)

An 8-minute video by udiprod about theory of computation and mathematical reasoning, on the Computer science shelf. It was posted to r/programming as “This is the greatest explanation of the Halting Problem I have ever seen, but people keep downvoting it because they don't understand and think it's wrong.”. It is pitched at intermediate level.

udiprod, Video, 8 min, 2013, on the Computer science shelf

Study notes

Intermediate, Proof. Step 3 of 3 in What computation is

Helpful first

• Basic idea of a program
• Logical contradiction

What it builds

• Describe a machine completely enough for another machine to analyze.
• Construct a program that does the opposite of a prediction.
• Use contradiction to establish a limit of computation.

Useful moments

• 2:14A complete machine blueprint
• 6:32The contradiction

Check yourself: Why does the self-referential counterexample rule out a universal halting predictor?

Notes are based on metadata, Reddit context and selected English caption passages. They are not a review of every claim in the video.