In response to “Psychological Fidelity” (Vol. 4, No. 2).

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.

Liesbeth De Mol is a CNRS researcher in epistemology, history, and philosophy of computer science, mathematics, and logic.

Allyn Jackson is an American writer and editor based in Germany.

  1. Emil Post, “Finite Combinatory Processes—Formulation 1,” Journal of Symbolic Logic 1, no. 3 (1936): 103–5. 
  2. Alonzo Church, “An Unsolvable Problem of Elementary Number Theory,” American Journal of Mathematics 58, no. 2 (April 1936): 345–63. 
  3. Emil Post, “Finite Combinatory Processes—Formulation 1,” Journal of Symbolic Logic 1, no. 3 (1936): 103. 
  4. See Liesbeth De Mol, “Generating, Solving and the Mathematics of Homo Sapiens: Emil Post’s Views on Computation,” in A Computable Universe: Understanding Computation and Exploring Nature as Computation, ed. Hector Zenil (Singapore: World Scientific, 2013), 45–62. 
  5. Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society s2-42, no. 1 (1937): 230–65. 
  6. This is in fact Post’s own responsibility. In his paper “Recursive Unsolvability of a Problem of Thue” (Journal of Symbolic Logic 12, no. 1 [1947]: 1–11), which is briefly discussed by Jackson in the section titled “Unsolvable Problems,” Post refers to Turing machines rather than his own formulation 1 in order to prove the recursive unsolvability of the word problem of semi-groups. However, it can be argued that Post’s representation of the Turing machine in this note has much in common with his own formulation 1, including the so-called quadruple notation and the need for a STOP order. See also Liesbeth De Mol, “Turing Machines,” The Stanford Encyclopedia of Philosophy, ed. Edward Zalta (2018). 
  7. Liesbeth De Mol, “Formalism(s): The Success(es) of a Failure,” in Soyons logique/Let’s Be Logical, ed. Amirouche Moktefi, Alessio Moretti, and Fabien Schang (London: College Publications, 2016), 31–48. 
  8. Emil Post, “Finite Combinatory Processes—Formulation 1,” Journal of Symbolic Logic 1, no. 3 (1936): 105, fn. 8. 
  9. Post’s original wording is “[The] purpose [of such formulations] is not only to present a system of a certain logical potency but also, in its restricted field, of psychological fidelity.” Emil Post, “Finite Combinatory Processes—Formulation 1,” Journal of Symbolic Logic 1, no. 3 (1936): 105. 
  10. This is described in the section titled “Beneath the Surface of Common Sense.” More details can be found in Alasdair Urquhart, “Emil Post,” in Handbook of the History of Logic, ed. Dov Gabbay and John Woods (Amsterdam: Elsevier/North-Holland, 2009), 5:617–66, and Liesbeth De Mol, “Formalism(s): The Success(es) of a Failure,” in Soyons logique/Let’s Be Logical, ed. Amirouche Moktefi, Alessio Moretti, and Fabien Schang (London: College Publications, 2016), 31–48. 
  11. Clarence Irving Lewis, A Survey of Symbolic Logic (Berkeley: University of California Press, 1918), 355. 
  12. This was at odds with Bertrand Russell and Alfred North Whitehead’s Principia Mathematica, which, according to Post, “gave up the generality of outlook which characterized symbolic logic.” Emil Post, “Introduction to a General Theory of Elementary Propositions,” American Journal of Mathematics 43, no. 1 (1921): 163. 
  13. Emil Post, “Introduction to a General Theory of Elementary Propositions,” American Journal of Mathematics 43, no. 1 (1921): 173. 
  14. Part of these results can be found in the published version of Post’s PhD dissertation: “Introduction to a General Theory of Elementary Propositions,” American Journal of Mathematics 43, no. 1 (1921): 163–85. Post’s lattice is described in Emil Post, The Two-valued Iterative Systems of Mathematical Logic (Princeton University Press, 1941). A detailed description of that work is given in Alasdair Urquhart, “Emil Post,” in Handbook of the History of Logic, ed. Dov Gabbay and John Woods (Amsterdam: Elsevier/North-Holland, 2009), 5:617–66. 
  15. Emil Post, “Introduction to a General Theory of Elementary Propositions,” American Journal of Mathematics 43, no. 1 (1921): 163–85. 
  16. Emil Post, “Absolutely Unsolvable Problems and Relatively Undecidable Propositions—Account of an Anticipation,” in The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, ed. Martin Davis (New York: Dover, 2004), 386. 
  17. For an explanation of some of these formal classes, see Allyn Jackson, “Emil Post: Psychological Fidelity,” Inference: International Review of Science 4, no. 2 (October 2018). 
  18. Emil Post, “Absolutely Unsolvable Problems and Relatively Undecidable Propositions—Account of an Anticipation,” in The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, ed. Martin Davis (New York: Dover, 2004), 386–87. 
  19. Emil Post, “Absolutely Unsolvable Problems and Relatively Undecidable Propositions—Account of an Anticipation,” in The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, ed. Martin Davis (New York: Dover, 2004), 384. 
  20. Emil Post, “Absolutely Unsolvable Problems and Relatively Undecidable Propositions—Account of an Anticipation,” in The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, ed. Martin Davis (New York: Dover, 2004), 430. Jackson’s mention of the problem in the section titled “The Reversal” is inaccurate and imprecise. Post did not talk about incomputable sets. For a precise statement of the result, see the quote by Post in point 1) in the text above. 
  21. Ivor Grattan-Guinness, “The Manuscripts of Emil L. Post,” History and Philosophy of Logic 11, no. 1 (1990): 82. 
  22. Emil Post, “Absolutely Unsolvable Problems and Relatively Undecidable Propositions—Account of an Anticipation,” in The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, ed. Martin Davis (New York: Dover, 2004), 378, fn. 12. 
  23. Emil Post, “Absolutely Unsolvable Problems and Relatively Undecidable Propositions—Account of an Anticipation,” in The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, ed. Martin Davis (New York: Dover, 2004), 394. 
  24. Emil Post, “Absolutely Unsolvable Problems and Relatively Undecidable Propositions—Account of an Anticipation,” in The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, ed. Martin Davis (New York: Dover, 2004), 394 
  25. Clarence Irving Lewis, A Survey of Symbolic Logic (Berkeley: University of California Press, 1918), 371. 
  26. Emil Post, “Finite Combinatory Processes—Formulation 1,” Journal of Symbolic Logic 1, no. 3 (1936): 105. 
  27. Supported by the ANR PROGRAMme grant ANR-17-CE38-0003-01.