The POPL Gatekeeper


6 October 2016

There is an obvious distinction to be made between computers (which include laptops and iPads) on the one hand and mathematical models on the other hand. Strictly speaking, it is wrong to say that “a computer is a finite state machine.” That's like speaking about a mathematical model as if it coincides with reality. Unfortunately, it is unusual to make these kinds of observations explicit in computer science, as I am doing now and as I have done in my paper entitled `Category Mistakes in Computer Science at Large.'

My paper on Category Mistakes was rejected by POPL referees for some very good reasons (albeit non-technical ones). I've introduced the POPL Gatekeeper in my previous post and the objective here is to discuss the following remark made by the Gatekeeper:

I'm not sure why CACM reviewers would ignore the difference between real-world systems and their mathematical models. I don't actually see that mistake in the quoted reviews.

I received this genuine comment on October 3rd, 2016. In my rejected POPL paper, I present quoted reviews from anonymous referees of the Communications of the ACM (CACM) — reviews that I received on January 24th, 2016, after having submitted a prior version of my rejected POPL paper to the CACM in the fall of 2015. (For the sociological record: the reviews received from the CACM are much more elaborate, they convey more how each reviewer thinks. The CACM referees have provided pages of feedback. In retrospect, this is perhaps to be expected. The CACM is after all a journal while “POPL” refers to an annual conference which has a well-defined scope of research.)

As I've mentioned in my previous blog post, I don't agree with the Gatekeeper's assessment. In my words:

I'm afraid reviewers of the CACM have applied faulty reasoning and I also believe I have illustrated precisely that in my POPL paper (but that's a topic I will address another day).

I will address that topic now. I will, however, only discuss a strict subset of all the CACM reviews that I cover in my rejected POPL paper. I will thus only present the basics here and leave the really interesting stuff for later.

Computers vs. Mathematical Models

The categorical distinction between computers and mathematical models often goes unnoticed. A computer is not a finite state machine. The former is a concrete physical object and it can be mathematically modeled by the latter, which is an abstract object. Well, here then is the first comment that I have received from a referee of the CACM:

My laptop is a universal Turing machine, but its tape size is of course limited by the finiteness of human resources.

If you limit the tape size of a universal Turing machine, you may end up with, say, a linear bounded automaton or even a machine that is computationally equivalent to a finite state machine. You thus end up with another mathematical model of computation but not with a laptop (i.e., a concrete physical object). To be more precise:

You can't use human resources to limit the size of a mathematical object, i.e., the tape. Note that the “tape” indeed denotes a mathematical object and not a physical object, contrary to what the word “tape” seems to suggest.

You can introduce mathematical restrictions to limit the size of a mathematical object. Likewise, you can use human resources to limit the size of a concrete physical object (such as a laptop). But, once again:

A Turing machine is a mathematical object, it is not a computer. This is contrary to what the word “machine” seems to suggest.

I know where the CACM reviewer is coming from. I, too, have been educated as a computer scientist and also used to speak about my mathematical model as if it coincides with reality. The right way to put it, once again, is as follows:

Placing finite bounds on an abstract object (Turing machine) does not make it a concrete physical object (laptop). Instead, it results in another abstract object (e.g., a linear bounded automaton or a finite state machine) that can potentially serve as another mathematical model for the physical object at hand.

I agree that these words convey a very trivial distinction. But missing the distinction can easily lead to faulty reasoning. For example, it makes no sense to say that a laptop is Turing complete. Only a mathematical model of computation can be Turing complete. Likewise, it makes no sense to question whether your iPhone is Turing complete or not. Unfortunately, these statements can be found all over the place, not only in peer reviews but also in articles and in books, published by reputable publishers. (I discuss several peer reviewed articles in my rejected POPL paper.) I've even had discussions with colleagues who start proving on the blackboard that my laptop is Turing complete. They really think they are giving a mathematical proof. As I emphasize in my (often rejected) writings:

It is the mathematical model of a laptop that may or may not be Turing complete, not the laptop itself. Yet, many computer scientists disagree with this statement and erroneously place both objects in the same category. This is where a category mistake occurs.

Comparing a laptop with a Turing machine is only warranted with the proviso that we all agree we are reasoning across separate categories.

Likewise, and as I have already illustrated to some extent in my previous blog posts, it makes no sense to claim, nor to attempt to mathematically prove, any of the following:

  1. The computer programming language C is Turing complete.
  2. The Halting Problem of computer programs residing in my laptop (or any laptop for that matter) is unsolvable.

I understand that many programming language experts view a “programming language” as a mathematical object. That's why I want to explicitly distinguish between a “computer programming language” and a “mathematical programming language.” I take C to be a computer programming language and I know that many computer scientists (= typically non programming language experts) who defend claim 1. do so too and, therefore, make a category mistake. In fact, they often simply do not distinguish between the computer programming language and their mathematical model. That is the main point I am repeatedly trying to make.

Abusing the Halting Problem

Grasping the significance of the observations made so far is not easy for here is yet another response that I have received from a referee of the CACM and which I have also reported in my rejected POPL paper:

What does the undecidability proof of the halting problem for computer programs actually tell us. Like diagonalization proofs in general it may be viewed finitely as saying that, if there is a bound M on the size of accessible computer memory, or on the size of computer programs, or any other resource, then no computer program subject to the same resource bounds can solve the problem for all such computer programs.

The previous remark and the follow-up remark, presented below, are only correct if we accept the following two assumptions (each of which is wrong):

  1. A computer program is a synonym for a mathematical program.
  2. The mathematical program (mentioned in the previous sentence) has to be equivalent to a Turing machine program and not to, say, a primitive recursive function.

The reason why the second assumption has to hold is merely because the referee is referring to the halting problem of Turing machines. Continuing:

If computer program A solves correctly all halting problems for computer programs respecting bound M, then the counterexample computer program T must exceed that bound, which is why A fails for T. To solve problems of computer programs, one needs an ideal program.

The quote hints at a distinction that has to be made between finite and infinite objects (with the latter being labeled “ideal”) but the categorical distinction between computer programs and mathematical programs goes unnoticed. Again, this is where a category mistake occurs. The undecidability proof of the halting problem is about mathematical programs only, and not about computer programs. The diagonal argument can only be applied to mathematical objects. So, to be frank, the referee thinks s/he is giving a mathematical argument but, in fact, s/he is demonstrating faulty reasoning. S/he is not proving something about computer programs but about a *particular* mathematical model of a computer program! So much for mathematical rigor.



what do you think I'm going to say? :-)

"The computer programming language C is Turing complete."

There is a distinction to be made between the C abstract machine as specified by the C standard and the myriad of particular implementations of C. When someone says "C is Turing complete (or not)", you should give them charitable reading and assume they're talking about the abstract machine. At least that's what *I* did (albeit to conclude that it's not Turing complete).

Good point

When analyzing the writings of different actors from a historical angle I try to understand how each actor uses, say, the term "programming language" without judgment. (My typical example pertains to four different views on programming: Dijkstra, Strachey, Parnas, and Naur.) So when somebody says "C is Turing complete" and doesn't start "proving" things about electronic technology in a particular way, then I don't see any problem with that statement.

There is a distinction to be made between the C computer programming language and several mathematical models of that technical artefact. Since in my philosophical analysis I try to follow Raymond Turner's terminology (which you can agree or disagree with) I, as an actor myself, do *not* consider the C programming language to refer to a mathematical machine. The C programming language is a technical artefact and not a mathematical object. Therefore it can be neither Turing complete nor incomplete.

From Turner's perspective, neither a laptop nor a computer programming language can be Turing complete (or incomplete).

Moreover, the fact that you (along with other like-minded researchers) prefer a Turing incomplete mathematical model for the C computer programming language and others prefer a Turing complete mathematical model, shows that a distinction is in order between the technical artefact under scrutiny and its mathematical models.

Whether the inventors of C were going for a Turing complete or incomplete model is an interesting historical question. My educated guess is that historical research will reveal that programming language designers "back then" were not at all concerned about Turing completeness to begin with. So the historical question is probably anachronistic.

There is also a distinction to be made between the C standard of the C computer programming language and the various implementations of the C standard. Both the C standard (e.g., written on paper) and each implementation (e.g., represented electronically) are technical artefacts, albeit of a very different kind.

R. Turner. Programming languages as technical artefacts. Philosophy and Technology, 27(3):377–397, 2014. First online: 13 February 2013. (See also the references in this paper.)