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

2 Responses to Why Programming is Hard

  1. Jay Cummings says:

    Nice post! Did you write this awhile ago or did you actually take a break from studying for your qual to write it? See you sometime next week! My schedule keeps changing to I still don’t know when precisely.

    • soffer801 says:

      I took a break from algebra to study logic, and thought this was worth sharing with the world. Then I took a break to hang out with a friend of yours.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s