A common question in amateur science forums goes like this: how long until we can fully automate computer programming, in the sense of telling the computer what we want it to do in a few English sentences? That’s a wonderful fantasy, but it goes beyond “technically infeasible” and into “doesn’t even make sense”. In this article we will argue why such perfectly automated computer programming is not just impossible, but doesn’t even make sense to imagine in our wildest dreams. You might expect me to say something about recursion theory or Turing completeness, but it’s actually much simpler than that, and any junior high age kid can understand it once properly explained. It’s just a matter of intuitively comparing the sizes of certain sets.

Consider your favorite video game. I’ll use “Final Fantasy 7″ but you can mentally replace that with whatever suits you. In the fantasy world where programming has been automated, we should be able to coerce a computer into generating FF7 just by giving it a few simple English sentences. Just describe FF7 to the computer, as you would to a friend, and the computer whips it up. But we will see this idea is absurd not just in a technical feasibility sense but in a basic logical sense. Let’s talk about minor FF7 variations: games just like FF7 but with some minor variation. For example, in the 1st screen after the intro movie, suppose you change the color of one single pixel. That produces an FF7 variation. In a pedantic sense, that one-pixel change creates a whole new game, albeit very close to the original. Or, take FF7 and change one line of the dialog (maybe correct one of the translation errors). Again, a whole new game, at least in some sense.

Now try and think about all the possible different minor variations of FF7. How many are there? Instead of changing one pixel, we could change two pixels, which really blows up the number of possible variations. If we’re allowed to change as many as a hundred pixels, suddenly the number of variations becomes cosmically huge, even though changing a hundred pixels barely alters the game.

As a mathematician and a combinatorialist, I’m tempted now to go off on a tangent and talk more specifically about just *exactly* how many game variations we could get by altering N pixels, etc. But I’ll fight that temptation, because those kinds of details aren’t really necessary, as we’ll see very soon. I’ll jump straight to the climax of the argument: the number of minor variations of FF7 is vastly, unimaginably huger than the number of short English descriptions we could possibly tell to a computer. To use some made up numbers: if there are 1000 minor variations of FF7, and only 100 short English descriptions, then there must necessarily be at least 900 variations that cannot be “programmed” by telling our omnicomputer a short English description. The exact numbers, 1000 and 100, aren’t important here, just that the former is a lot bigger than the latter. There are a lot more variations on my favorite game, than there are variations on a half-hour English-language description of the same, and that means that most of the variations are unprogrammable via casual description.

To clinch the argument, it’s necessary for me to convince the reader that FF7 has far more minor variations than there are short English descriptions of video games. After all, if there are far more game-variations than English descriptions, then those English descriptions can’t possibly hit any more than a tiny sliver of the possible variations of the game. Now, you might expect me to whip out some exact calculations involving counting arguments, but as I said before, it’s not necessary. There’s a way to short-circuit all the computations.

Short circuit: Suppose you have some short English description of an FF7-variation. Let’s call that description, X. So maybe X is the English description: “Computer, please create a game just like FF7 except that the light in Room #4 is one shade dimmer.” Now let me describe a silly, seemingly unrelated, other variation of FF7 to you, I’ll call this silly variation X’. The game X’ is exactly like FF7 with only one difference: in the first building, there’s a new NPC who, if you talk to him, he says the following dialog: “Computer, please create a game just like FF7 except that the light in Room #4 is one shade dimmer.” That is, this new NPC, who lives in the game X’, recites your description X as his dialog.

While obviously rather silly, my variation X’ is overall a pretty minor variation of the game. We can repeat this construction no matter what description X you come up with. If you choose X to be the description, “Computer, make a version of FF7 where RedXIII is a cat,” then I’ll counter it with a variation X’ of the game where the first building has an NPC who says, “Computer, make a version of FF7 where RedXIII is a cat”. Thus, no matter what English description you come up with, I’m able to “counter” it with a very special type of variation, one where the only change is a new NPC in the first building. Now, among all possible minor variations of FF7, those variations of the form “Add a new NPC to the first building”, make up a very tiny part. And yet, that very tiny part of all variations, is able to cover all the English descriptions you can think up. I’ve covered all the English descriptions while barely scratching the surface of the space of all possible game variations.

The above two paragraphs prove the following claim: The number of minor variations of FF7 is far, far, far huger than the number of simple English descriptions. This claim has the following consequence: If we automate computer programming, so we can tell a computer a simple English description and have it make the corresponding program, then we must necessarily “miss” the ability to program tons and tons of possible variations of games. If there are 999,999,999 different variations of a game, and only 999,999 simple English descriptions, then necessarily we’ll have to resort to old-fashioned techniques of programming in order to get the computer to run 999,000,000 of those variations.

That’s why programming isn’t just hard to automate—isn’t just impossible to automate—but why in fact, it doesn’t even make logical sense to imagine automating computer programming. If a science fiction author describes a futuristic world where people have invented new numbers so flexible that 100 of these new numbers suffice to count up to 1000 objects, then he’s broken your suspension of disbelief: you craaazy, Mr. Asimov! But that’s ultimately what “automated programming” boils down to, by the above argument: a fantasy where 100 English descriptions suffice to program 1000 programs (I’ve underestimated the exact numbers here!)

Pre-emptive responses to critics
“But what if the computer can read your mind, in order to fill in the gaps!” If the computer is capable of mind reading, that changes things, and maybe then it is possible to “automate programming”. But the result we get isn’t really programming at all. A computer program (in this case the simple English phrases I say to my computer) isn’t really a computer program if its results depend on who invokes it (if a different person says the same simple phrases to her computer, she’ll get a different program, because the computer reads different things out of her mind). Anyway, we still haven’t automated programming, we’ve just abstracted it from “something you do with your fingers” to “something you do with your mind”.
“Your argument isn’t logically rigorous!” Absolutely correct. Notions like “English sentence” are notoriously informal, otherwise we could destroy the universe by talking about “the smallest number that can’t be described in ten words”. The point of this article isn’t to be mathematically formal, but to present the argument to laymen.
That concludes the article, thank you for reading. Now let me say a few words to my laptop. Dear laptop, please listen for HTTP connections on port 80, and respond with an article about why programming is hard to automate, based on comparing sizes of sets intuitively, using a self-referential short-circuit, and aimed at a casual audience. And, go!

Link ~> http://www.xamuel.com/programming-hard-to-automate/