# halting problem

#### Simple halting problem proof found in SICP^{1}:

Exercise 4.15.Given a one-argument procedure`p`

and an object`a`

,`p`

is said to ``halt’’ on`a`

if evaluating the expression`(p a)`

returns a value (as opposed to terminating with an error message or running forever). Show that it is impossible to write a procedure`halts?`

that correctly determines whether`p`

halts on`a`

for any procedure`p`

and object`a`

. Use the following reasoning: If you had such a procedure`halts?`

, you could implement the following program:`(define (run-forever) (run-forever)) (define (try p) (if (halts? p p) (run-forever) 'halted))`

Now consider evaluating the expression (try try) and show that any possible outcome (either halting or running forever) violates the intended behavior of halts?

**Case 1:**

Procedure `try`

halts when passed itself as input. Hence, halts? would return
true and `try`

would loop forever — a contradiction.

**Case 2:**

Procedure `try`

loops forever. Hence, `halt?(try, try)`

returns false, `try`

halts on input `try`

— a contradiction.

#### Cantor Diagonalization^{2}:

A program is really just one big number, which means that all possible programs are countably infinite. So, for the sake of contradiction, suppose an oracle exists that solves the halting problem. First we list out all of the possible programs. Next, we can create a grid by listing all the possible inputs for each program on the adjacent axis.

A B C D E …All all possible inputs on X-axis.A B C D E …All possible programs on Y-axis.

Each program, when run on each input, will either halt or loop forever, thus our outputs will fill the table, e.g.

A B C D E AHL H L H B HHH H H C L HLH H D H L LLH E H H H LHH: Halts, L: Loops

Now, we create a new row by taking the elements at the diagonal (i.e the first element from the first row, the second element from the second row, etc.) and flipping Halt to Loop and Loop to Halt.

L L H H L

**Where does this new row appear on the list?**
It cannot appear on the list because it is different from each row by at least
one element.

This table is defined as the complete list of all possible programs and inputs,
but we can never write a program that matches this new row for *all* inputs.

Cantor Diagonalization is actually very similar to the first proof. The `try`

procedure does the opposite of what each program does, just as we constructed
the row from the diagonal, and the `halt?`

procedure is the oracle. We assumed
that the oracle exists, but have shown that it cannot exist. Hence, we have
proven by contradiction that the halting problem is undecidable.