Inside the ComputerComputability Theory

The Halting Problem

Some questions no computer will ever be able to answer

Your laptop freezes and you wonder: is it working or stuck forever? Why can't any program ever tell for sure?

You'll find out

  • A tiny program nobody can predict
  • The trick that traps any predictor
  • Why virus scanners can't be perfect

Why it matters

It's why no tool can catch every bug or virus, or always tell a frozen app from a busy one.

About 4 min7 interactive slides · 5 questionsLesson 629 · Zone 70

Play this lesson

Free to play in your browser or on iPhone

More in this zone

  1. 622Set TheoryBanach–TarskiCut a ball into pieces and reassemble two identical balls
  2. 623Mechanical Energy StorageThe FlywheelA spinning wheel can store energy in its motion
  3. 624Number TheoryThe Prime SpiralWrite numbers in a spiral and primes line up in diagonals
  4. 625Data StorageWhy SSDs Wear OutEvery save slightly damages a flash memory cell
  5. 626Depth PerceptionParallaxNearby things move faster than distant ones, and that's how we see depth
  6. 627Matching MarketsThe Kidney ChainAlgorithms link strangers so more transplants happen
  7. 628Swarm RoboticsA Thousand Robots, No LeaderSimple machines can organize themselves with local rules
  8. 630Bayesian ReasoningThe Doomsday ArgumentYour birth order might be evidence about humanity's future