# Computability (Ch 10)¶

The idea of proving that CanCrash.exe can’t exist is pretty mind-bending. This video might be helpful - it walks through the logic on why we can’t write a program that detects if a program Halts (stops running at some point):

Also, this Wired article has a nice overview of the problem and argument. It also has a fun Dr. Seuss style poem explaining the Halting Problem:

No general procedure for bug checks will do.

Now, I won’t just assert that, I’ll prove it to you.

I will prove that although you might work till you drop,

you cannot tell if computation will stop.For imagine we have a procedure called P

that for specified input permits you to see

whether specified source code, with all of its faults,

defines a routine that eventually halts.

### Optional: Turing Machines

The most amazing feature of Turing’s Proof that the Halting Problem and similar **decision problems** are uncomputable is that he did his work before modern computers existed. He had to invent a theoretical universal computer to make his argument. This machine, known as a **Turing Machine** is a fundamental model for computation - anything that can be computed with any conceivable computer algorithm can be computed on a Turing machine. This video has a nice introduction to this idea of a Turing Machine: