[The Association for Symbolic Logic], 1936.
First edition, very rare offprint, of Post’s formulation of the notions of computation and solvability by means of a theoretical machine very similar to the concept of a Turing machine proposed by Alan Turing in his famous paper ‘On computable numbers.’ Alonzo Church had, slightly earlier, identified effective calculability with general recursiveness and λ-definability [‘An unsolvable problem in elementary number theory,’ American Journal of Mathematics 58 (1936), 345-363]. The formulations of Church, Post and Turing were later shown to be equivalent, but while Church’s and Turing’s identifications are now famous under the heading ‘the Church-Turing thesis’, Post’s formulation is less well known. Intending the model of computation presented in this paper as the first of a series of models of equivalent power but increasing complexity, Post titled his paper Formulation I. On the occasion of Post’s death in 1954, W. V. Quine wrote: “Modern proof theory, and likewise the modern theory of machine computation, hinge on the concept of a recursive function. This important number-theoretic concept, a precise mathematical substitute for the vague idea of “effectiveness” or “computability,” was discovered independently and in very disparate but equivalent forms by four mathematicians, and one of these was Post. Subsequent work by Post was instrumental to the further progress of the theory of recursive functions” (DSB).
“In 1936, [Alonzo] Church founded a new quarterly devoted to contemporary research in logic: The Journal of Symbolic Logic. Its first volume contained a three-page paper by Emil L. Post, “Finite Combinatory Processes: Formulation 1”. The editors added a footnote to the paper that read: “Received October 7, 1936. The reader should compare an article by A. M. Turing, On computable numbers, shortly forthcoming in Proceedings of the London Mathematical Society. The present article, however, although bearing a later date, was written entirely independently of Turing’s.” Post (1897-1954) was at the time teaching at City College in New York City and had also contact with Church, both personal and through correspondence.
“As to the remark concerning Post’s paper, it would indeed be readily apparent to any reader of Turing’s and Post’s articles that their basic idea of “computation” was the same. Turing presented a machine model; his machines were “supplied with a ‘tape’ … divided into sections, called ‘squares’, each capable of bearing a ‘symbol’” from a finite list, possibly just two different ones. In the latter case we refer to the machine as a two-letter machine. Instead of a tape divided into squares, Post wrote of a “symbol space … to consist of a two way infinite sequence of spaces or boxes”; each box could be either “marked” or “unmarked”. In both conceptions, at a given instant, one particular square/box was in play, and the permitted basic operations were to change the symbol in the square/box and/or to move to an adjacent square/box. Turing imagined these steps carried out by a simple mechanism with a finite number of states where each step included a possible change of state. In Post’s formulation, the computation is carried out by a human “worker” who is following a fixed sequence of instructions including what we would call a conditional jump instruction. The jump instruction is also part of a program for Turing’s machine; depending on the symbol in the square and its state, the machine may follow a different next instruction” (Sommaruga & Strahm, pp. 4-5).
In his paper Post did not, unlike Turing, prove the unsolvability of the Entscheidungsproblem (‘decision problem’), probably because he was aware that this had already been settled by Church in ‘An unsolvable problem in elementary number theory’. However, Post had in fact come close to solving this problem, as well as the incompleteness problem settled by Gödel, more than a decade earlier. “In 1920-1921 [Post] held a post-doctoral fellowship at Princeton. During this time he tried to analyse the whole Principia [Mathematica, 1910-13], with a view to proving its completeness and consistency as he had done for propositional calculus. This was the most ambitious project possible, because the axioms of Principia were thought to imply all theorems of mathematics. Nevertheless, Post made some progress: He showed that all theorems of Principia (and probably of any conceivable symbolic logic) could be derived by simple systems of rules he called normal systems … Sometime in 1921, as he later claimed, he caught a glimpse of the true situation:
- Normal systems can simulate any symbolic logic, indeed any mechanical system for deriving theorems.
- This means, however, that all such systems can be mechanically listed, and the diagonal argument then shows that the general problem of deciding whether a given theorem is produced by a given system is unsolvable.
- It follows, in turn, that no consistent mechanical system can produce all theorems.
“These discoveries of Post include (in different form) the discoveries of Turing on the nature of computability and unsolvability, and Gödel’s theorem on the incompleteness of formal systems for mathematics.
“The really big problem, in Post’s view, was to show that all computation is reflected in normal systems. Without a precise definition of computation, the concept of unsolvable problem is meaningless” (Stillwell).
In 1921, Post suffered an attack of bipolar disorder. The condition recurred frequently, often requiring hospitalization, and prevented his from obtaining an academic position until 1935. “By this time Post had seen two of his greatest ideas rediscovered by others. In 1931 Gödel published his incompleteness theorem, and in 1935 Church stated Church’s thesis, which proposes a definition of computability and implies the existence of unsolvable problems. Church’s definition of computability was not immediately convincing (at least not to Gödel), and some equivalent definitions were proposed soon after. The one that convinced Gödel was Turing’s, now known as the Turing machine. Post’s normal systems, another equivalent of the computability concept, were still unpublished. But this time Post had a little luck. Independently of Turing, and at the same time, he had reformulated his concept of computation, and had found a concept virtually identical with Turing’s! It was published in a short paper in the 1936 Journal of Symbolic Logic, with a note from Church affirming its independence from Turing’s work … so in fact he completed his program in 1936. By then, unfortunately, it was too late for him to get credit for anything except a small share of the computability concept. Thus Post’s proof of incompleteness was delayed because he was trying to do so much: the task he set himself in 1921 was in effect to do most of what Gödel, Church, and Turing did among them in 1931-36.
“[The present paper] gave Post some recognition, but he was still in Turing’s shadow. Turing had written a fuller paper, with clearer motivation and striking theorems on the existence of a universal machine and unsolvable problems. The world knew that Post had also found the definition of computation, but did not know that he had already seen the consequences of such a definition in 1921. In 1938, he met Gödel and tried to tell him his story. Perhaps the excitement was too much for Post, because he seems to have feared that he had not made a good impression. The next day, October 29, 1938, he sent Gödel a postcard that reads as follows:
“I am afraid that I took advantage of you on this, I hope but our first meeting. But for fifteen years I had carried around the thought of astounding the mathematical world with my unorthodox ideas, and meeting the man chiefly responsible for the vanishing of that dream rather carried me away.
“Since you seemed interested in my way of arriving at these new developments perhaps Church an show you a long letter I wrote to him about them. As for any claims I might make perhaps the best I can say is that I would have proved Gödel’s theorem in 1921 had I been Gödel”” (Stillwell).
“As Turing left the subject of pure computability theory in 1939, his mantle fell on Post. Post continued the tradition of clear, intuitive proofs, of exploring the most basic objects such as computability and computably ennumerable sets, and, most of all, of exploring relative computability and Turing reducibility. During the next decade and a half, from 1940 until his death in 1954, Post played an extraordinary role in shaping the subject” (Soare, p. 242).
Soare, Turing Computability: Theory and Applications, 2016; Sommaruga & Strahm, Turing’s Revolution: The Impact of His Ideas about Computability, 2016; Stillwell, ‘Emil Post and His Anticipation of Gödel and Turing,’ Mathematics Magazine 77 (2004), pp. 3-14.
Offprint from The Journal of Symbolic Logic, Vol. 1, No. 3, September 1936, pp. 103-105. 8vo (255 x 179 mm), pp. 103-105 [1:blank], original printed wrappers, a virtually mint copy.