September 19, 2020

Still More on Programs vs. Data

My previous postings on the program vs. data distinction have drawn quite a few comments. (To see them, click the “followups” links on my previous postings.) I’m going to let the conversation settle a bit before commenting again. But just to stir things up, here is another challenging case.

Some programs are never meant to be executed. They do instruct a computer to do something, but their author never intends them to be executed, and they never are executed. Why would somebody write a program that they know will never be executed? Let me explain.

Suppose you are studying mathematical logic, and you want to know whether a particular assertion can be proven from some set of initial axioms. It turns out that there is a deep equivalence between mathematical logic and programming languages, such that a given statement is provable in a logic if and only if a computer program of a certain type exists. It follows that you can show that a statement is provable by demonstrating the existence of a certain type of program. You don’t have to run the program; you just have to show that it is a valid program according to the rules of a particular programming language.

This isn’t just a theoretical parlor trick. Researchers often use this equivalence to show the provability of logical statements by exhibiting the existence of programs. I myself have done this and have published two papers about it. In the course of doing this, I wrote lots of program code, but never once did I run any of it.

If you believe that the author’s intent is what makes something a program, then the code I wrote is not a program, since I never meant it to control a computer (and it never did). If, on the other hand, you believe that program-ness is inherent in the potential capability of the object itself, then my code is a program.