## Why Programming is Hard

Take your favorite programming language and write a program in it. Your compute stores the source code as a string of zeros and ones. We can interpret that code as a number in binary. So to each program, we have a number. We may have many numbers whose programs that do the same thing, but any program I can write down has a number associated with it. Let $P_e$ be the program which is encoded by $e$. This might not do anything. It might have lots of spelling mistakes and syntactical errors, but every program is $P_e$, for some number $e$.

Programs take in inputs and spit out outputs. Or at least, sometimes they do. Sometimes programs run forever. Suppose I am handed a bunch of programs and told to run them on some inputs, but I’m told I only have an hour to do this. Obviously I can’t run the ones that go one forever, so how do I know which ones those are? How do I tell the difference between a program that runs for an obscenely long time, and one that will never end?

The short of it is that I can’t. There is no algorithmic way to determine which programs halt and which programs run forever.

Theorem: There is no program $H$ which takes input $e$ (an encoding of a program) and $x$ (some input to the program encoded by $e$), and spits out $1$ if $P_e(x)$ halts and $0$ otherwise.

Proof: Suppose I had such a program. I’m going to make a slightly different program. What it will do is take in some input $e$, and determine whether or not $P_e(e)$ halts. If $P_e(e)$ never halts, it will return $17$. Otherwise, it will enter an infinite loop and never halt. This program sometimes stops and sometimes goes without stopping, so we’ll call it the “Yielding Program.” Here’s some pseudocode for that program:

To save space, I’m going to write $Y$ for the “yielding program,” and I’m going to let $p$ be the number encoding it. That is, $Y=P_p$. Ready for the magic? Does $Y(p)$ halt? That is, does $Y(p)$ return $17$? If it did, that would mean that we were in the first case in the if-statement, so $H(p,p)=0$. But $H(p,p)=0$ means that $P_p(p)$ (a.k.a. $Y(p)$) doesn’t halt. That’s a contradiction.

What about the other possibility $Y(p)$ goes on forever. This means that $H(p,p)$ is not $0$, so it must be $1$. But this too is a problem, for then $P_p(p)$ (a.k.a. $Y(p)$) does halt. That’s another contradiction.

Since we used the existence of a program $H$ to construct $Y$, which lead to a contradiction, it must be that $H$ cannot not really exist.

$\square$

If you didn’t like this proof, then  perhaps this one in a Dr. Seuss style will suit you better: Scooping the Loop Snooper