To the editors:
In a three-page paper titled “Finite Combinatory Processes—Formulation 1,” Emil Leon Post proposed a formalization of the intuitive notion of solvability.1 He wrote this note after having read Alonzo Church’s 1936 paper that contains Church’s thesis.2 As Post explains in the beginning of his note, “We have in mind a general problem consisting of a class of specific problems. A solution of the general problem will then be one which furnishes an answer to each specific problem.”3 He presents formulation 1 as such a solution.
This identification between solvability and formulation 1 has been called Post’s second thesis.4 The formulation proposed by Post is quite similar to Turing’s machines, and because of that, it has been largely ignored in favor of Alan Turing’s lengthier 1936 paper “On Computable Numbers with an Application to the Entscheidungsproblem,” which contains more results.5 Instead of reducing Post’s contribution to its relation with Church’s or Turing’s formulations, one might well ask, why did Post decide to publish this note after having read Church’s paper and why did he not use the formulation he already had in 1921 and which he had left unpublished? Allyn Jackson’s essay only partially tackles this question.
Two sections are devoted to Post’s note. The first, titled “Surpassed by Turing,” considers in what ways Post’s formulation relates to Turing’s. The fact that Post later criticized Turing’s formulation in favor of his own, is not mentioned.6 In a second section, titled “Not a Definition, a Natural Law,” Jackson describes how Post understood his and Church’s identifications to be different. As I have argued in another publication, to Church, the identification of effective calculability with general recursive functions (and lambda-definability) is a formal definition.7 Post, however, understood solvability and calculability as human capabilities:
[T]o mask this identification under a definition hides the fact that a fundamental discovery in the limitations of the mathematicizing power of Homo Sapiens has been made and blinds us to the need of its continual verification.8
By consequence, identification is not just a formal definition but rather a scientific hypothesis about human abilities that needs continual verification. Put differently, the purpose of any such formulation is not to develop a system with only a certain logical potency, as seems to be the case with Church, but also with psychological fidelity.9 Fundamental in that viewpoint is not so much a naturalist attitude, as is suggested by Jackson, but its implicit view of logic as a human activity. This point, not emphasized by Jackson, is essential to understanding Post’s work on computability and unsolvability. It explains why Post continued work on this subject for about thirty years, despite having already formed his own results in the early 1920s and witnessed the publications of Church’s and Turing’s papers. This brings me back to the above question about Post’s motivations to publish his note: Why did he not use his original thesis from 1921 that anticipated the results of Church, Turing, and Kurt Gödel?
In that earlier work, Post had developed his own methods and research program rooted in combining two research traditions, algebraic logic and mathematical logic. His program was inspired by C. I. Lewis’s A Survey of Symbolic Logic and, more specifically, Lewis’s so-called heterodox view on mathematics, also called mathematics without meaning.10 The heterodox view defines a mathematical system as
any set of strings of recognizable marks in which some of the strings are taken initially and the remainder derived from these operations performed according to rules which are independent of any meaning assigned to the marks.11
Post adopted this viewpoint not as a philosophical position per se, but as a guiding methodology to tackle problems about all of mathematics.12 In order to achieve generality, Post developed two main “instruments of generalization”: generalization by truth-tables and generalization by postulation.13 The former resulted in Post’s multi-valued logic and Post’s lattice.14 The latter resulted in the first of a series of classes of production systems that Post later called the canonical form A. This series is a generalization of his formulation of propositional logic as given during his PhD.15
Initially, these methods were successful and allowed Post to achieve several positive results within the framework of propositional logic. But since it was Post’s aim to provide results about all of mathematics, his attention soon shifted to what he considered to be a fundamental problem of all deductive systems: finding a general finite method to determine for any formalized mathematical system and a given statement thereof, whether or not that statement can be derived from the postulates of that system by finite means. He called this the finiteness problem. An obvious starting point was the logic of Principia Mathematica—basically first-order logic. Post was proposing no less than to find a positive solution to the well-known Entscheidungsproblem for first-order logic. This became the main purpose of his postdoctoral fellowship at Princeton from 1920 to 1921. He tackled this problem by using the method of combinatory iteration, which is basically Lewis’s heterodox interpretation of mathematics. Post described it as follows:
[The method of combinatory iteration] eschews all interpretation, and studies the system merely as a formal system. The operations of the system are then described as “combinatory” since they largely involve but a reshuffling of symbols; and it is through the “iteration,” i.e., continued reapplication, of these combinatory operations that the entire system is obtained.16
The application of this method led Post to develop a sequence of classes of formal systems, starting with the systems in canonical form A, then systems in canonical form B, systems in canonical form C, systems of the form of ‘tag,’ and systems in normal form where each can be seen as a generalization by simplification of (one of the) former (with the exception of the form of ‘tag’).17 The aim was not to find the simplest possible form through the method of combinatory iteration, as Jackson suggests, but, instead, to use that method to tackle the finiteness problem. In brief, Post realized two things:
1) The finiteness problem for the class of systems in normal form is unsolvable. That is,
there is no finite method which would uniformly enable us to tell of an arbitrary normal system and arbitrary sequence on the letters thereof whether that sequence is or is not generated by the operations of the system from the primitive sequence of the system.18
2) Post’s Thesis I: the class of systems in normal form is able to capture all finite generative systems, namely, formal systems that produce finite words. This is rooted in Post’s normal form theorem, the proof that for any set of sequences generated by a system in canonical form C, one can set up a system in normal form which also generates those sequences. As Post explains:
for if the meager formal apparatus of our final normal systems can wipe out all of the additional vastly greater complexities of canonical form B, the more complicated machinery of the latter should clearly be able to handle formulations correspondingly more complicated than itself.19
On this basis, Post became convinced that the finiteness problem for the class of systems in normal form is unsolvable in the absolute sense: there exists no human finite method to solve the finiteness problem for the class of normal systems. This result, which Jackson mentions only in passing, Post considered to be a fundamental result of his earlier work; in his words, “The writer cannot overemphasize the fundamental importance to mathematics of the existence of absolutely unsolvable combinatory problems.”20
Instead, Jackson emphasizes Post’s other result from that time, the incompleteness of symbolic logic, which is a partial anticipation of Gödel’s incompleteness results. But Post considered his own incompleteness result “a corollary of my finite process analysis.”21
Of course Post did not think incompleteness was irrelevant. On the contrary, and as Jackson correctly emphasizes, it was incompleteness that led him to conclusions about mathematics as being essentially a human, creative activity. Another fundamental insight is not considered by Jackson. Post explains,
[A]s this account emphasizes, the creativeness of human mathematics has a counterpart inescapable limitation thereof—witness the absolutely unsolvable (combinatory) problems. Indeed, with the bubble of symbolic logic as universal logical machine finally burst, a new future dawns for it as the indispensable means for revealing and developing those limitations. … Symbolic Logic may be said to be Mathematics become self-conscious.22
The reversal Jackson discusses is not so much about the creativeness insight, but rather about the realization of this fundamental limitation which leads to that creativeness conclusion as a corollary. This insight led Post to the conclusion that in order for his earlier thesis to obtain full generality, it would not suffice to prove only that, for instance, first-order logic reduces to systems in normal form; instead, “a complete analysis [should] be made of all the possible ways the human mind [can] set up finite processes for generating sequences.”23
From here, we can understand Post’s remark, in the 1936 article, that the purpose of his and other formulations is to develop a system of not only logical potency but psychological fidelity as well, since “[e]stablishing [the] universality [of the results] is not a matter for mathematical proof, but of psychological analysis of the mental processes involved in combinatory mathematical processes.”24
It is exactly here that one finds also a reference, conscious or unconscious, to Lewis’s work, which had been so important to Post. In the concluding chapter of his book, Lewis speculates: “Perhaps a wider use of logistic would help to free science from a considerable body of ‘hypotheses’ whose value lies not in their logical implications but in their psychological ‘suggestiveness.’”25
Post had shown that at the heart of logic, there is a hypothesis whose value lies in both its logical implications and its implied limitations for humans. This is why in 1936 he finally published his short note, which contains traces of his analysis of finite processes with which he also started in the 1920s and left unpublished. He would later continue work on this hypothesis even though he was already convinced of it. He realized that it required further study. Evidence for this can be found in the thousands of pages of notebooks in which he worked on the program. He announced in the 1936 note the need to consider “wider and wider contemplations” of formulation 1, that is, a formulation 2.26 He continued his work in logic as a means to reveal and develop the limitations implied by the hypothesis. Much of his later published work, including his founding paper on recursion theory and his work on the existence of absolutely undecidable propositions, can be understood from that perspective.
Jackson’s essay leaves the reader with a sense that Post was a great mathematician who suffered due to his personal and professional circumstances. The perception of Post was colored as a result. He was seen as a second-class mathematician who had been surpassed by Gödel and Turing. Nonetheless, we should be careful not to let such historical assessments determine our own views. Post was certainly undervalued, but that need not mean that we can only study his work relative to the work of those considered first-class. On the contrary, it is by studying Post as a first-class mathematician that one can truly appreciate his contributions. One such contribution that I have hinted at here is that it was not Turing or Gödel, but Post, who reflected most deeply on issues of absolutely unsolvable problems. He proposed an open-ended research program that was abandoned upon his death and which, hopefully, will be picked up by future scholars.27
Liesbeth De Mol
Allyn Jackson replies:
It is gratifying to have such thoughtful and edifying reactions. Many thanks to Graham Leach-Krouse and Liesbeth de Mol for sharing their knowledge and insights.
