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

Advertisements