The prehistory of generative grammar and Chomsky’s debt to Emil Post

1.1A few terminological preliminaries

I should clarify the sense of some crucial terms before I begin, because many terminological traps have been set by linguists for the unwary over the past 60 years. Those well acquainted with formal linguistics and theoretical computer science can skip over this fairly swiftly.

2.1Separating syntax from semantics

Urquhart (2009)Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier.Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier. notes that Whitehead and Russell in PM ‘fail to make the basic distinction between axioms and rules of inference’, classing both as ‘Primitive Propositions’. The PM counterpart of the inference rule classically known as Modus Ponens (the one that licenses inferring ‘q’ from the premises ‘p⊃q’ and ‘p’) was a ‘primitive proposition’ stating that ‘Anything implied by a true elementary proposition is true’ (Vol. 1, p. 94). This need not be regarded as a mistake on their part — it might be intuitively helpful as a part of their task of simultaneously saying what the formulæ are and explaining what they mean — but it does not strictly separate derivability of symbol strings (syntax) from truth conditions for propositions (semantics). The philosopher-logician Clarence Irving Lewis (1883–1964) thought it would be useful to make such a strict separation.22.Interestingly, one of Lewis’s PhD students at Harvard was Nelson Goodman, who would later have Noam Chomsky as one of his students in philosophy classes at the University of Pennsylvania.

Post began his PhD studies at the age of 21 in the year 1918 (ten years before Chomsky was born). It was in that year that Lewis published an important book called A Survey of Symbolic Logic. In a section present only in the first edition (pp. 354ff)33.Lewis required the last two chapters of his book to be omitted from the later Dover edition, having apparently lost confidence in the value of the novel material those chapters introduce. he sets out what he calls a ‘heterodox’ approach to logic (it is not so heterodox today). Instead of treating propositional reasoning in a way that appeals to intuitions about meaning, as in PM, he proposes making a strict separation of the symbol manipulations accomplished by ‘rules of inference’ from any consideration of their semantic purpose, and states a logic as a ‘mathematical system’, which he defines as a ‘set of strings of recognizable marks in which some of the strings are taken initially and the remainder derived from these by operations performed according to rules which are independent of any meaning assigned to the marks’ (p. 355).

Consider, then, a conventional propositional logic using the symbols {∼,∨,⊃} plus parentheses ‘(’ and ‘)’ and a supply of propositional variables p ₁,p ₂,p ₃, etc. Lewis suggests that to ensure we know exactly what conclusions are provable from our premises we should make no use of anything like the intuitions familiar from translations into English: that ∼ means ‘not’, ∨ means ‘or’, ⊃ means ‘implies’, that parentheses are for grouping, etc.; rather, the meanings of the symbols should be set aside, and you should imagine you are simply given a list of one or more basic strings formed from these symbols (intuitively, those would be your axioms, basic assumptions not needing to be derived — but ignore that for now), together with a set of operations for adding new strings to the list (which intuitively corresponds to proving theorems). Then Modus Ponens (also known as Detachment) will say something like this (here I condense and paraphrase from Lewis 1918Lewis, C. I. 1918 A Survey of Symbolic Logic. Berkeley, CA: University of California Press, first ed.. Lewis, C. I. 1918 A Survey of Symbolic Logic. Berkeley, CA: University of California Press, first ed.. : 357):

• Find a string φ on the list that begins with ‘(’, ends with ‘)’, and contains ‘⊃’.

• Now find another string on the list that is identical with the bit of φ between the ‘(’ and the ‘⊃’ characters.

• You may now add to the list the bit of φ that follows ‘⊃’, removing its final ‘)’.

Thus if ‘α⊃β’ is already on the list and so is ‘α’ you are permitted to add ‘β’ to the list (no matter what the form of α and β might be). When we come to consider the semantics, this will correspond to making an argument step such as (to give an example in loose, informal English) taking ‘if the power is out then we can’t serve hot food’ and ‘the power is out’, and drawing the logical consequence ‘we can’t serve hot food.’

Lewis was proposing that the syntactic business (mapping out how strings could be derived from other strings) should be kept entirely separate from the semantics (which meanings are understood as necessary consequences of which other meanings), and then it should be shown that these notions nonetheless coincide in their effects.

Post took up Lewis’s approach to proof as manipulation of symbol strings independently of meaning or truth, and framed it more rigorously (notice that he refers to Lewis’s book in the third footnote of the published version of his PhD thesis, Post 1921Post, Emil L. 1921 “Introduction to a General Theory of Elementary Propositions”. American Journal of Mathematics 43:3.163–185. Reprinted in van Heijenoort (1967: 264–283) and reproduced in Davis (1994b: 21–43). Post, Emil L. 1921 “Introduction to a General Theory of Elementary Propositions”. American Journal of Mathematics 43:3.163–185. Reprinted in van Heijenoort (19671: 264–283) and reproduced in Davis (1994b: 21–43). ). He observes that PM ‘gave up the generality of outlook which characterized symbolic logic’, and states that he will be concerned with ‘the recovery of this generality’ (p. 1́63). Accordingly, in his PhD dissertation he worked out the following three things:

1. a procedure for deriving new symbol strings from antecedently available strings, independently of whatever logical interpretation or truth value any string might have assigned to it (this is the role of his production systems); and

2. a rigorous truth table method for determining that a formula is a tautology;44.Post draws his method from earlier literature, including William Stanley Jevons (1835–1882), John Venn (1834–1923), and before them, George Boole (1815–1864), all of whom he mentions. Ludwig Wittgenstein (1889–1951) employed truth tables in the Tractatus Logico-Philosophicus, but the first publication of that work, under the title ‘Logisch-Philosophische Abhandlung’, was in Annalen der Naturphilosophie 14, in 1921, so it could not have been an influence on Post’s PhD work. Charles Sanders Peirce (1839–1914) employed truth tables as early as 1883, in unpublished work (see Anellis 2012Anellis, Irving H. 2012 “Peirce’s Truth-functional Analysis and the Origin of the Truth Table”. History and Philosophy of Logic 33:1.87–97. Anellis, Irving H. 2012 “Peirce’s Truth-functional Analysis and the Origin of the Truth Table”. History and Philosophy of Logic 33:1.87–97. ). Post would not have known about this directly, but it could have influenced him indirectly via the teaching of his PhD supervisor, who was an early friend and promoter of Peirce. Indeed, Post seems to have decided, some twenty years after his PhD dissertation was published, that his primary debt was indeed to Keyser: the dedication page of Post (1941)Post, Emil L. 1941 The Two-Valued Iterative Systems of Mathematical Logic. Princeton NJ: Princeton University Press.Post, Emil L. 1941 The Two-Valued Iterative Systems of Mathematical Logic. Princeton NJ: Princeton University Press. reads: ‘Dedicated to Cassius J. Keyser[,] in one of whose pedagogical devices the author belatedly recognizes the true source of his truth-table method.’

3. a proof that from the axioms of PM, using the syntactic proof method it assumes, you can derive a formula (i.e., prove that it is a theorem) if and only if the truth-table method defines it as a tautology.

This is undergraduate logic material today, but in 1921 all three parts were highly original work, and provided foundations for further important results (see the beautifully clear introduction to the 1921 published version of Post’s PhD dissertation in van Heijenoort 1967Van Heijenoort, Jean 1967 From Frege to Gödel: A source book in mathematical logic, 1879–1931. Cambridge, MA: Harvard University Press.Van Heijenoort, Jean 1967 From Frege to Gödel: A source book in mathematical logic, 1879–1931. Cambridge, MA: Harvard University Press.: 264–265, and the more recent study by Urquhart 2009Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier.Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier.). It is item (I), the syntactic procedure for deriving new strings from given ones, that will be our focus here.

2.2From propositional to first-order logic

Post’s dissertation dealt with just the propositional component of PM’s logic, but the plan for his postdoctoral year (1920–21) on a Procter Fellowship at Princeton was to extend his results further, to the whole of the first-order logic used in PM (that is, including the formulæ involving quantifiers like ‘all’ and ‘some’), and find a decision procedure for theoremhood. (For the propositional calculus he had already obtained this.)

What happened instead was that after a year work on the problem, Post had run into what seemed like a roadblock. Though ultimately, reconceptualizing the roadblock revealed an insight profound enough to trigger a complete reversal of his goals and launch a whole new field of mathematics.

What Post discovered was that it looked as if it was never going to be possible to find a procedure for deciding whether an arbitrary expression of first-order logic could be derived by the operations of a set of string-rewriting operations from some other such string. There appeared to be cases in which even radically simplified string-rewriting operations could not be associated with any systematic method for determining in finite time what they would do. The work of discovering this was maddening (all too literally, as we shall see), but eventually Post saw that he had made a discovery that would doom any general program of reducing mathematics to decidable questions of logic. To have both completeness and consistency for any logic rich enough to express the truths of a domain like arithmetic was impossible.

What this means is that by the fall of 1921 he had at least glimpsed the truth of the three most fundamental results that would later be achieved in 20th-century mathematical logic:

• Kurt Gödel (1906–1978) would show in 1931Gödel, Kurt 1931 “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I”. Monatshefte für Mathematik und Physik 38:1.349–360. Translated as “On Formally Undecidable Propositions of Principia Mathematica and Related Systems, I”. In van Heijenoort 1967, 596–616.Gödel, Kurt 1931 “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I”. Monatshefte für Mathematik und Physik 38:1.349–360. Translated as “On Formally Undecidable Propositions of Principia Mathematica and Related Systems, I”. In van Heijenoort 19671, 596–616. that a particular class of consistent axiom systems for number theory was necessarily incomplete, i.e., there would always be unprovable arithmetical truths. A detailed formulation of the general insight about formal systems that Post was hoping to produce would have Gödel’s result as a corollary.

• Alonzo Church (1903–1995), in a 1936Church, Alonzo 1936 “An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics 58:2.345–363. Church, Alonzo 1936 “An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics 58:2.345–363. paper, showed that the Endscheidungsproblem — the problem of providing a decision procedure for first-order mathematical theories — could have no general solution. He did it by presenting the first absolutely unsolvable problem in pure mathematics: the problem of determining whether two different lambda-calculus formulæ are interconvertible.

• Alan Turing (1912–1954), by the end of the same year, gave the first completely convincing demonstration (the one that convinced Gödel) that there were computational problems that would never submit to a general solution method implementable on a finite computing machine, no matter what its power or design.

Ten years before Gödel’s proof, then, Post knew that he was on the edge of results that would extinguish the hope expressed by David Hilbert in 1920 when he claimed that ‘in mathematics there is no ignorabimus’: that ultimately all mathematical truths would turn out to be within the reach of the human intellect.

2.3Publish or perish: The years of illness

Tragically, Post was unable to achieve publication of his radically important findings in the 1920s.55.For biographical details in what follows I rely on Post (1941[1965])Post, Emil L. 1941[1965] “Absolutely Undecidable Problems and Relatively Undecidable Propositions — Account of an Anticipation”. Rejected by American Journal of Mathematics in 1941; posthumously published in Davis (1965: 340–433); reprinted in Davis (1994: 375–441).Post, Emil L. 1941[1965] “Absolutely Undecidable Problems and Relatively Undecidable Propositions — Account of an Anticipation”. Rejected by American Journal of Mathematics in 1941; posthumously published in Davis (1965: 340–433); reprinted in Davis (1994: 375–441). and several secondary sources: Davis (1994), Stillwell (2004)Stillwell, John 2004 “Emil Post and his Anticipation of Gödel and Turing”. Mathematics Magazine 77:1.3–14. Stillwell, John 2004 “Emil Post and his Anticipation of Gödel and Turing”. Mathematics Magazine 77:1.3–14. , De Mol (2006)De Mol, Liesbeth 2006 “Closing the Circle: An analysis of Emil Post’s early work”. Bulletin of Symbolic Logic 12:2.267–289. De Mol, Liesbeth 2006 “Closing the Circle: An analysis of Emil Post’s early work”. Bulletin of Symbolic Logic 12:2.267–289. , Urquhart (2009)Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier.Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier., and Jackson (2018)Jackson, Allyn 2018 “Emil Post: Psychological fidelity”. Inference: International Review of Science 4:2. Online at https://​inference​-review​.com​/article​/psychological​-fidelityJackson, Allyn 2018 “Emil Post: Psychological fidelity”. Inference: International Review of Science 4:2. Online at https://​inference​-review​.com​/article​/psychological​-fidelity. He believed that his ideas could never be persuasive to mathematicians without a full analysis of the sources of incompleteness and undecidability in formal systems and logics in general — a task far broader than the one that Gödel would later take up. He desperately wanted to carry on with his groundbreaking research, but instead he was stricken with mental health problems.

Toward the end of his productive year at Princeton, as he ran into the puzzle of extremely simple rewriting systems that are bafflingly intractable — the very intractability that ultimately led to his revolutionary insight — Post began to exhibit symptoms of fairly severe bipolar disorder: excitement over his mathematical results on computational intractability pushed him into a state of mania. His behavior was alarming enough that he was hospitalized for a time.

He had succeeded in obtaining an instructor position in mathematics at Cornell for the year 1921–22, and managed to move to Ithaca, take up the post, commence teaching, and make a small amount of further progress (he did submit a paper to Annals of Mathematics in 1922, though it was rejected). But soon a recurrence of his illness forced him to resign from the job and return to his parents’ home in Harlem, where for a decade he earned his living as a mathematics teacher at the George Washington High School in New York. Under medical advice he disciplined himself strictly to do no more than three hours of mathematical research per day, with a walk afterwards to calm him down. He would alternate between two projects, switching to a second problem if his work on the first was getting him too excited. He seems to have done some work in 1924, 1925, and 1929 (Davis 1982Davis, Martin 1982 “Why Gödel didn’t Have Church’s Thesis”. Information and Control 54:1.3–24. Davis, Martin 1982 “Why Gödel didn’t Have Church’s Thesis”. Information and Control 54:1.3–24. : 22).

After at last obtaining a faculty position at the City College of New York in 1932, he again had to resign, within a month. Only in 1935 was he able to return to City College, where his teaching turned out to be popular and successful, despite a tough teaching load (16 contact hours a week, and none of the time or facilities for research that today’s research universities provide). And by then the world of mathematical logic was changing fast. After Gödel, Post had been irrevocably overtaken, and he knew it.

In 1936 he did manage to publish a short note in which he gave a detailed abstract design for a method of computing that involves no operations other than (i) writing a symbol in a box on an indefinitely large workspace, (ii) erasing such a symbol, (iii) moving left or right to a new box, and (iv) moving to a new instruction according to the answer to a yes/no question about the symbol in the current box. He conjectures (correctly, it turned out later, though he did not provide a proof in the paper) that this suffices as a model for computing any computable function. It is remarkably similar to the model of computation that Turing had independently developed and had submitted for publication four months earlier, though Post had no knowledge of Turing’s work.

Some time later, Post decided to write a long historical and biographical paper (Post 1941[1965]Post, Emil L. 1941[1965] “Absolutely Undecidable Problems and Relatively Undecidable Propositions — Account of an Anticipation”. Rejected by American Journal of Mathematics in 1941; posthumously published in Davis (1965: 340–433); reprinted in Davis (1994: 375–441).Post, Emil L. 1941[1965] “Absolutely Undecidable Problems and Relatively Undecidable Propositions — Account of an Anticipation”. Rejected by American Journal of Mathematics in 1941; posthumously published in Davis (1965: 340–433); reprinted in Davis (1994: 375–441).) detailing his anticipation of the results of Gödel, Church, and Turing, and sent it to the American Journal of Mathematics in 1941, but it was rejected by the editor, Hermann Weyl, who ruled that the journal was ‘no place for historical accounts.’ The paper was saved from oblivion by Martin Davis (1928–2023), once an undergraduate student of Post’s at City College and later a PhD advisee of Alonzo Church, who became a distinguished computability theorist; he published it in an anthology on undecidable problems (Davis 1965Davis, Martin ed. 1965 The Undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions. New York: Raven Press. Reissued 2004 by Dover Publications with a different version of the final paper by Post.Davis, Martin ed. 1965 The Undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions. New York: Raven Press. Reissued 2004 by Dover Publications with a different version of the final paper by Post.) and included it in his edition of Post’s complete works (Davis 1994). Weyl suggested, however, that Post should submit a shorter paper presenting the crucial new result (which he had basically obtained by the fall of 1921). That suggestion resulted in the crucial paper called ‘Formal reductions of the general combinatory decision problem’’ (Post 1943Post, Emil L. 1943 “Formal Reductions of the General Combinatory Decision Problem”. American Journal of Mathematics 65:2.197–215. Reproduced in Davis (1994b: 442–460). Post, Emil L. 1943 “Formal Reductions of the General Combinatory Decision Problem”. American Journal of Mathematics 65:2.197–215. Reproduced in Davis (1994b: 442–460). ), which I will henceforth refer to as Reductions. It contains the first full presentation of the rewriting systems Post had developed for formalizing inference, but also proves an entirely original generative capacity theorem about their expressive power: the Normal-Form Theorem, which I discuss later (§ 4.1).

4.1The Normal-Form Theorem

The first major theorem that he was able to publish as a step toward this goal was a result in what in mathematical linguistics (following Chomsky) is called ‘weak generative capacity’ and among logicians is referred to as expressive power. The result, basically obtained by the fall of 1921 but not published until 1943, was the main result published in Reductions. Through a complex series of manipulations reducing the complexity of rewriting operations at each step, Post showed that provided additional auxiliary symbols are permitted in derivations (symbols that can be manipulated by the operations but are not allowed in generated strings),1010.The auxiliary symbols are what Chomsky would later call ‘nonterminal’ symbols. The A and B in the Brainerd and Landweber example above exemplify these. They are not indexed variables over strings, but fixed arbitrary symbols that appear in the sentential forms of a grammar but not in the generated stringset. See Footnote 7. every set that can be generated by a canonical production system can be generated by a vastly simplified form.

Chomsky’s MIT colleague in computer science, Marvin Minsky (1927–2016), refers to this theorem of Post’s as ‘one of the most beautiful theorems in mathematics’, and he provides a simpler proof of it (Minsky 1967Minsky, Marvin L. 1967 Computation: Finite and infinite machines. Englwood Cliffs, NJ: Prentice-Hall.Minsky, Marvin L. 1967 Computation: Finite and infinite machines. Englwood Cliffs, NJ: Prentice-Hall.: 240–251). Here is what the theorem says (with Post’s use of ‘produce(s)’ replaced by ‘⇒’, as above):

In the terms that would have been used in the early days of transformational grammar, the theorem says that provided that transformations can manipulate non-terminals, and can delete a specified sentence-initial formative and/or append a specified formative to the end of a string, any set of sentences that has a finite grammar at all can be generated by a transformational grammar.1111.I try to mininize the use of technical terms from computability theory in this paper, but it may be helpful to note that I take these terms to be synonyms: ‘generated set’ (meaning a set generated by some Post production system); ‘recursively enumerable’ or ‘r.e.’ set; ‘computably enumerable’ or ‘c.e.’ set (Soare 1996Soare, Scott 1996 “Computability and Recursion”. Bulletin of Symbolic Logic 2.284–321. Soare, Scott 1996 “Computability and Recursion”. Bulletin of Symbolic Logic 21.284–321. ); and ‘computably listable’ set (Epstein and Carnielli 2000Epstein, Richard L. & Walter A. Carnielli 2000 Computability: Computable functions, logic, and the foundations of mathematics. Belmont, CA: Wadsworth, 2nd ed.Epstein, Richard L. & Walter A. Carnielli 2000 Computability: Computable functions, logic, and the foundations of mathematics. Belmont, CA: Wadsworth, 2nd ed.). I avoid using the words ‘recursion’ and ‘recursive’ wherever possible because of their unhelpful ambiguity; see Tomalin (2007Tomalin, Marcus 2007 “Reconsidering Recursion in Syntactic Theory”. Lingua 117.1784–1800. Tomalin, Marcus 2007 “Reconsidering Recursion in Syntactic Theory”. Lingua 1171.1784–1800. : 1796–1799) for a useful discussion of the ambiguity.

This profound theorem of Post’s has been almost entirely overlooked even within mathematical linguistics. It predicts in broad outline the core results of several independent studies of transformational-generative grammars in the 1960s. It provides a justification for the confidence with which Putnam made this remark (1961Putnam, Hilary 1961 “Some Issues in the Theory of Grammar”. Structure of Language and Its Mathematical Aspects, number XII in Proceedings of Symposia in Applied Mathematics ed. by Roman Jakobson, 25–42. Providence, RI: American Mathematical Society. Putnam, Hilary 1961 “Some Issues in the Theory of Grammar”. Structure of Language and Its Mathematical Aspects, number XII in Proceedings of Symposia in Applied Mathematics ed. by Roman Jakobson, 25–42. Providence, RI: American Mathematical Society. : 41):

Chomsky’s general characterization of a transformational grammar is much too wide. It is easy to show that any recursively enumerable set of sentences could be generated by a transformational grammar in Chomsky’s sense.

Putnam does not hint at a proof of this ‘easy’ result. Post’s Normal-Form Theorem would have pointed the way to one, but he does not mention Post.

Later in the 1960s various proofs were published showing in various ways that Putnam was right: Kimball (1967)Kimball, John 1967 “Predicates Definable over Transformational Derivations by Intersection with Regular Languages”. Information and Control 11:1–2.177–195. Kimball, John 1967 “Predicates Definable over Transformational Derivations by Intersection with Regular Languages”. Information and Control 11:1–2.177–195. , Ginsburg and Hall-Partee (1969)Ginsburg, Seymour & Barbara Hall-Partee 1969 “A Mathematical Model of Transformational Grammar”. Information and Control 15:4.297–334. Ginsburg, Seymour & Barbara Hall-Partee 1969 “A Mathematical Model of Transformational Grammar”. Information and Control 15:4.297–334. , Salomaa (1971)Salomaa, Arto 1971 “The Generative Capacity of Transformational Grammars of Ginsburg and Partee”. Information and Control 18:3.227–232. Salomaa, Arto 1971 “The Generative Capacity of Transformational Grammars of Ginsburg and Partee”. Information and Control 18:3.227–232. , and Peters and Ritchie (1971Peters, P. Stanley & Robert W. Ritchie 1971 “On Restricting the Base Component of Transformational Grammars”. Information and Control 18:5.483–501. Republished in Mathematical Systems Theory 6, 324–333 1973 Peters, P. Stanley & Robert W. Ritchie 1971 “On Restricting the Base Component of Transformational Grammars”. Information and Control 18:5.483–501. Republished in Mathematical Systems Theory 61, 324–333 1973 , 1973Peters, P. Stanley & Robert W. Ritchie 1973 “On the Generative Power of Transformational Grammars”. Information Sciences 6.49–83. Peters, P. Stanley & Robert W. Ritchie 1973 “On the Generative Power of Transformational Grammars”. Information Sciences 61.49–83. ). Given the Normal Form Theorem, the theorems these mathematical linguists proved were at the very least extremely plausible from the start. I am not implying that they had no work to do: they had to capture exactly the operations and conditions Chomsky permitted in transformational grammars at the time, because those operations and conditions could in principle have turned out to incorporate some limitation or other preventing certain kinds of derivation. But Chomsky’s transformational grammars could clearly erase designated terminal symbols (the ‘recoverability of deletion’ condition proposed by Katz and Postal 1964Katz, Jerrold J. & Paul M. Postal 1964 An Integrated Theory of Linguistic Descriptions. Cambridge, MA: MIT Press.Katz, Jerrold J. & Paul M. Postal 1964 An Integrated Theory of Linguistic Descriptions. Cambridge, MA: MIT Press.: 80–81 is not violated), and likewise could insert specified terminal symbols, so the Normal Form theorem points the way quite directly.

Seymour Ginsburg was one of the five students who took a legendary undergraduate honors class taught by Post at City College (circa 1948; see Urquhart 2009Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier.Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier.: 471; Martin Davis was also in the class); yet even the Ginsburg and Hall-Partee paper does not cite Post, or mention production systems or the Normal Form Theorem.1212.The Normal Form Theorem also seems likely to predict other results in logic. Humberstone (2008)Humberstone, Lloyd 2008 “Replacing Modus Ponens with One-premiss Rules”. Logic Journal of the IGPL 16:5.431–451. Humberstone, Lloyd 2008 “Replacing Modus Ponens with One-premiss Rules”. Logic Journal of the IGPL 16:5.431–451. , for example, investigates the consequences of replacing Modus Ponens by inference operations using only one premise. Normal-form operations always have just one premise, so by Post’s theorem this should always be possible without loss of inferences.

4.2Axel Thue’s unsolvable word puzzle

Later Post proved a second generative capacity theorem, crucially important to Chomsky’s 1959Chomsky, Noam 1959 “On Certain Formal Properties of Grammars”. Information and Control 2(2):137–167. Reprinted in Readings in Mathematical Psychology, Volume II, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 125–155. New York: John Wiley & Sons 1965 (citation to the original on p. 125 of this reprinting is incorrect). Chomsky, Noam 1959 “On Certain Formal Properties of Grammars”. Information and Control 2(2):137–167. Reprinted in Readings in Mathematical Psychology, Volume II1, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 125–155. New York: John Wiley & Sons 1965 (citation to the original on p. 125 of this reprinting is incorrect). paper but not cited. The paper was entitled ‘Recursive unsolvability of a problem of Thue’ (Post 1947Post, Emil L. 1947 “Recursive Unsolvability of a Problem of Thue”. Journal of Symbolic Logic 12:1.1–11. Reproduced in Davis (1965: 293–303) and in Davis (1994b: 503–512). Post, Emil L. 1947 “Recursive Unsolvability of a Problem of Thue”. Journal of Symbolic Logic 12:1.1–11. Reproduced in Davis (1965: 293–303) and in Davis (1994b: 503–512). ), and I will henceforth refer to it as Unsolvability.

Alonzo Church, editor of the Journal of Symbolic Logic, had suggested to Post that his methods might permit a solution to a problem posed in 1914 by the Norwegian mathematician Axel Thue (1863–1922). It concerns finite sets of symmetric substring replacement operations, e.g. ‘x may be replaced by y or vice versa’, which we can abbreviate as ‘x≈y’.

Call two strings ‘interconvertible’ under a set of such operations if and only if either string can be converted into the other via a chain of replacements that the operations permit. Thue posed this question: Is there an algorithm for determining whether two arbitrary strings of letters are interconvertible under a given finite set of operations? For example, suppose the operations allowed are these:

Are the words genius and fool interconvertible? Thue asked whether an algorithm could guarantee to decide such questions in a finite number of steps.

Post proved that the answer was negative: no such algorithm can exist. If you try out chains of operations, you might hit on a solution for a specific case through ingenuity or guesswork or accidental good luck (I leave the puzzle above as as an exercise for the reader), but the problem is not routinizable like long division: no computer program could ever be written that would guarantee to solve arbitrary problems of this sort in finite time.

Post noted first that a set of Thue operations is equivalent to a set of non-symmetric productions in what he called ‘semi-Thue’ form. Using his notation for operational variables covering the left and right ends of the string, these operations have the form ‘P ₁   g ₁   P ₂  ⇒  P ₁   g ₂   P ₂’ for specified g ₁ and g ₂. A system of Thue-style operations is equivalent to a semi-Thue set in which for every production P ₁ x P ₂ ⇒ P ₁ y P ₂ the set also happens to contain the inverse production P ₁ y P ₂ ⇒ P ₁ x P ₂.

Post proceeded to show that semi-Thue operations are capable of simulating Turing-machine computations. Specifically, a set of semi-Thue operations could be written such that some string σ ₁ would be relatable to a string σ ₂ under a given set of operations if and only if a certain Turing machine will ever write 0 on its output tape. Turing (1936)Turing, Alan M. 1936 “On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society Series 2, 42:1.230–265. Received 28 May 1936; read 12 November 1936. Correction published in PAMS series 2, 43.544–546 1937.Turing, Alan M. 1936 “On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society Series 2, 42:1.230–265. Received 28 May 1936; read 12 November 1936. Correction published in PAMS series 2, 431.544–546 1937. had proved that the latter problem is unsolvable; hence Thue’s problem is unsolvable.1313.The notion of unsolvability was of interest internationally at the time. Andrey Andreyevich Markov Jr. (1903–1979) independently proved the unsolvability of Thue’s problem in a paper submitted in the Soviet Union just 11 days after Post’s Unsolvability: Markov (1947)Markov, Andrey A. 1947 “Névozmožnost’ nékotoryh algorifmov v téorii associativnyh sistém” (‘Impossibility of certain algorithms in the theory of associative systems’). Doklady Akadémii Nauk SSSR 55:587–590. Abstracted by Andrzej Mostowski in Journal of Symbolic Logic 13:1.52–53 1948.Markov, Andrey A. 1947 “Névozmožnost’ nékotoryh algorifmov v téorii associativnyh sistém” (‘Impossibility of certain algorithms in the theory of associative systems’). Doklady Akadémii Nauk SSSR 55:587–590. Abstracted by Andrzej Mostowski in Journal of Symbolic Logic 13:1.52–53 1948.. And he based his proof on Post’s work (see Mostowski’s review of Markov’s paper in Journal of Symbolic Logic 13 no. 1, 1948, p. 52).

Post actually relied on his own independently developed analysis of computation (Post 1936Post, Emil L. 1936 “Finite Combinatory Processes — Formulation 1”. Journal of Symbolic Logic 1:3.103–105. Reproduced in Davis (1965: 288–291) and in Davis (1994b: 103–105). Post, Emil L. 1936 “Finite Combinatory Processes — Formulation 1”. Journal of Symbolic Logic 1:3.103–105. Reproduced in Davis (1965: 288–291) and in Davis (1994b: 103–105). ), rather than that of Turing’s brilliant but flawed 1936Turing, Alan M. 1936 “On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society Series 2, 42:1.230–265. Received 28 May 1936; read 12 November 1936. Correction published in PAMS series 2, 43.544–546 1937.Turing, Alan M. 1936 “On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society Series 2, 42:1.230–265. Received 28 May 1936; read 12 November 1936. Correction published in PAMS series 2, 431.544–546 1937. paper, and in an appendix to Unsolvability he provided a detailed analysis of the errors and infelicities in Turing’s paper.

Summarizing, between 1920 and 1947 Post developed rewriting systems of full transformational-generative power and proved not only that they had equivalent expressive power to Turing machines but also that they they had the same expressive power when their rules were radically restricted to one-premise forms, either ‘ g ₁ P ⇒ P g ₂’ or ‘P ₁ g ₁ P ₂ ⇒ P ₁ g ₂ P ₂’. However, as yet there was no connection between this mathematical work and any application in linguistics. I return to that topic in § 5.4.

5.1On the technical term ‘generate’

As far as I have been able to determine, the very first occurrence of the term ‘generate’ within linguistics to denote the relation between a grammar and the sentences of the stringset it describes is in the revised version of Chomsky’s 1951 MA thesis, completed in December 1951 after he had met Bar-Hillel and spent several months at Harvard, where we read this (Chomsky 1951bChomsky, Noam 1951b Morphophonemics of Modern Hebrew. Typescript of a radical revision of Chomsky’s MA thesis, dated December 1951; retyped and published by Garland, New York 1979.Chomsky, Noam 1951b Morphophonemics of Modern Hebrew. Typescript of a radical revision of Chomsky’s MA thesis, dated December 1951; retyped and published by Garland, New York 1979.: 3):

It is assumed that the sole purpose of the grammar is to generate a closed body of sentences, those having been already determined. Hence the grammar must be designed in such a way as to be the most efficient, economical, and elegant device generating just these sentences.

The sentence is on p. 3 of both the original typescript and the 1979 retyped version published by Garland. It was not in the version submitted to the University of Pennsylvania as Chomsky’s MA thesis in June of that year (Chomsky 1951aChomsky, Noam 1951a Morphophonemics of Modern Hebrew. Master’s thesis, University of Pennsylvania, Philadelphia, PA.Chomsky, Noam 1951a Morphophonemics of Modern Hebrew. Master’s thesis, University of Pennsylvania, Philadelphia, PA.).

No one seems to have used the word ‘generate’ in this way within linguistics before. It was only three years later that Charles Hockett (1916–2000) wrote about ‘principles by which one can generate any number of utterances in the language’ (Hockett 1954Hockett, Charles F. 1954 “Two Models of Grammatical Description”. Word 10:1.210–231. Page references are to the reprinting in Joos (ed.) 1966, 386–399. Hockett, Charles F. 1954 “Two Models of Grammatical Description”. Word 10:1.210–231. Page references are to the reprinting in Joos (ed.) 19661, 386–399. : 390) and Chomsky’s PhD mentor Zellig Harris (1909–1992) stated that ‘A grammar may be viewed as a set of instructions which generates the sentences of a language’ (Harris 1954Harris, Zellig S. 1954 “Transfer Grammar”. International Journal of American Linguistics 20:4.259–70. Harris, Zellig S. 1954 “Transfer Grammar”. International Journal of American Linguistics 20:4.259–70. : 260).

The term ‘generate’ does not appear in the relevant sense in Harris’s earlier work Methods in Structural Linguistics (completed by the end of 1946 but not published until 1951Harris, Zellig S. 1951 Methods in Structural Linguistics. Chicago, IL: University of Chicago Press. Republished as Structural Linguistics 1960 Preface dated January 1947.Harris, Zellig S. 1951 Methods in Structural Linguistics. Chicago, IL: University of Chicago Press. Republished as Structural Linguistics 1960 Preface dated January 1947.), a book which is significant because it provided Chomsky’s initiation into linguistics: he read it in 1947, when Harris gave him an early version in proof form (see Chomsky 1975Chomsky, Noam 1975 The Logical Structure of Linguistic Theory. New York: Plenum. Revision of Chomsky (1955–1956).Chomsky, Noam 1975 The Logical Structure of Linguistic Theory. New York: Plenum. Revision of Chomsky (1955–1956).: 25). Harris writes of ‘statements which enable anyone to synthesize or predict utterances in the language’, the statements forming ‘a deductive system with axiomatically defined initial elements and with theorems concerning the relations among them’, those theorems serving to ‘indicate the structure of the utterances of the language’ (Harris 1951Harris, Zellig S. 1951 Methods in Structural Linguistics. Chicago, IL: University of Chicago Press. Republished as Structural Linguistics 1960 Preface dated January 1947.Harris, Zellig S. 1951 Methods in Structural Linguistics. Chicago, IL: University of Chicago Press. Republished as Structural Linguistics 1960 Preface dated January 1947.: 372–73), remarks which clearly prefigure the idea of a generative grammar, as Seuren (1998Seuren, Pieter A. M. 1998 Western Linguistics: An historical introduction. Oxford: Basil Blackwell. Seuren, Pieter A. M. 1998 Western Linguistics: An historical introduction. Oxford: Basil Blackwell. : 228) notes (‘Here we have, in nucleo, the concept of generative grammar’); but the term ‘generate’ does not occur there, and neither Harris nor Chomsky made any reference to Post at the time. (Harris probably knew of Post’s work; forty years later he stated that “The expectation of useful mathematical description of the data of language stems from developments in logic and the foundations of mathematics during the first half of the twentieth century” and mentions “the specific constructionist techniques of Emil Post”: Harris 1991Harris, Zellig S. 1991 A Theory of Language and Information: A mathematical approach. Oxford: Clarendon Press. Harris, Zellig S. 1991 A Theory of Language and Information: A mathematical approach. Oxford: Clarendon Press. : 145).

Chomsky continued to use the term ‘generate’, occasionally employing Post’s other term ‘produce’ instead. For example, in Syntactic Structures he suggests on p. 11 that a grammar ‘can be viewed as a device of some sort for producing the sentences of the language under analysis’, and on p. 13 he says that the grammar of a language L will be ‘a device that generates all of the grammatical sequences of L and none of the ungrammatical ones.’

In 1959 ChomskyChomsky, Noam 1959 “On Certain Formal Properties of Grammars”. Information and Control 2(2):137–167. Reprinted in Readings in Mathematical Psychology, Volume II, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 125–155. New York: John Wiley & Sons 1965 (citation to the original on p. 125 of this reprinting is incorrect). Chomsky, Noam 1959 “On Certain Formal Properties of Grammars”. Information and Control 2(2):137–167. Reprinted in Readings in Mathematical Psychology, Volume II1, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 125–155. New York: John Wiley & Sons 1965 (citation to the original on p. 125 of this reprinting is incorrect). published a paper in which he was much more explicit about the mathematics of rewriting systems than he had been before, and in that paper he does cite a paper by Post. Apropos of investigating the structure of a stringset by studying ‘the finite devices (grammars) which are capable of enumerating its sentences’ (p. 137), he adds: ‘Such devices have been called “sentence-generating grammars”,’ and he attaches a footnote which says: ‘Following a familiar technical use of the term “generate,” cf. Post (1944)Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). .’ The term would only really have seemed ‘familiar’ to those who had been reading Post.1414.The footnote proceeds to say that the term ‘generate’ has ‘been misleading, since it has erroneously been interpreted as indicating that such sentence-generating grammars consider language from the point of view of the speaker rather than the hearer’ when in truth ‘such grammars take a completely neutral point of view.’ I will ignore this issue, and also his further remarks about a grammar of L being ‘a function mapping the integers onto L’, which seems to me to be clearly a mistake (rewriting systems are not functions taking integer arguments).

The paper Chomsky cites is ‘Recursively enumerable sets of positive integers and their decision problems’, and it is probably Post’s best-known paper, a beautifully written informal but far-sighted survey of the foundations of what would become computability theory and the theory of degrees of unsolvability. It was presented to the American Mathematical Society as an invited lecture on February 26, 1944 and submitted for publication on March 25. It is incredibly rich, and I find it hard to imagine what it must have been like for even a sophisticated mathematical audience to listen to it delivered orally. After reading it, one finds that a textbook like Hartley Rogers’ Theory of Recursive Functions and Effective Computability (1967Rogers, Hartley 1967 Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press.Rogers, Hartley 1967 Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press.) reads like an extended commentary on that one paper of Post’s. However, the paper gives only a skeletal presentation of production systems (pp. 286–287 [= pp. 464–465 of Davis 1994]).

5.2Chomsky’s acknowledgements of Post

In various subsequent works, Chomsky has occasionally mentioned Post’s name, but with no details and usually without citing any reference. I know of eight such cases.

• In three of his works (Chomsky 1959Chomsky, Noam 1959 “On Certain Formal Properties of Grammars”. Information and Control 2(2):137–167. Reprinted in Readings in Mathematical Psychology, Volume II, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 125–155. New York: John Wiley & Sons 1965 (citation to the original on p. 125 of this reprinting is incorrect). Chomsky, Noam 1959 “On Certain Formal Properties of Grammars”. Information and Control 2(2):137–167. Reprinted in Readings in Mathematical Psychology, Volume II1, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 125–155. New York: John Wiley & Sons 1965 (citation to the original on p. 125 of this reprinting is incorrect). : 137n, 1961Chomsky, Noam 1961 “On the notion ‘rule of grammar’.” Proceedings of the Twelfth Symposium in Applied Mathematics, 6–24. Providence, RI: American Mathematical Society. Reprinted in The Structure of Language: Readings in the philosophy of language ed. by Jerry A. Fodor & Jerrold J. Katz, 155–210. Englewood Cliffs, NJ: Prentice-Hall. Chomsky, Noam 1961 “On the notion ‘rule of grammar’.” Proceedings of the Twelfth Symposium in Applied Mathematics, 6–24. Providence, RI: American Mathematical Society. Reprinted in The Structure of Language: Readings in the philosophy of language ed. by Jerry A. Fodor & Jerrold J. Katz, 155–210. Englewood Cliffs, NJ: Prentice-Hall. : 7, and 1965Chomsky, Noam 1965 Aspects of the Theory of Syntax. Cambridge, MA: MIT Press.Chomsky, Noam 1965 Aspects of the Theory of Syntax. Cambridge, MA: MIT Press.: 9) he attributes the use of the verb ‘generate’ to Post, citing Post (1944)Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). in the first two cases.

• In his paper at the 1960 International Congress of Logic, Methodology and Philosophy of Science (Chomsky 1962Chomsky, Noam 1962 “Explanatory Models in Linguistics”. Logic, Methodology and Philosophy of Science: Proceedings of the 1960 International Congress ed. by Ernest Nagel, Patrick Suppes & Alfred Tarski, 528–550. Stanford, CA: Stanford University Press.Chomsky, Noam 1962 “Explanatory Models in Linguistics”. Logic, Methodology and Philosophy of Science: Proceedings of the 1960 International Congress ed. by Ernest Nagel, Patrick Suppes & Alfred Tarski, 528–550. Stanford, CA: Stanford University Press.: 539) he states that ‘A rewriting rule is a special case of a production in the sense of Post’, though he gives no reference.

• In his masterful survey of early-sixties mathematical linguistics (Chomsky 1963Chomsky, Noam 1963 “Formal Properties of Grammars”. Handbook of Mathematical Psychology, Volume II, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter 323–418. New York: Wiley.Chomsky, Noam 1963 “Formal Properties of Grammars”. Handbook of Mathematical Psychology, Volume II1, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter 323–418. New York: Wiley.: 382), he gives a brief account of ‘a problem that was proven to be recursively unsolvable by Post (1946)Post, Emil L. 1946 “A Variant of a Recursively Unsolvable Problem”. Bulletin of the American Mathematical Society 524.264–268. Reproduced in Davis (1994b: 495–500). Post, Emil L. 1946 “A Variant of a Recursively Unsolvable Problem”. Bulletin of the American Mathematical Society 5241.264–268. Reproduced in Davis (1994b: 495–500). , called the correspondence problem.’ Reduction to that problem provides a useful method for proving certain properties of grammars undecidable, as Chomsky shows. (His exposition closely follows that of Bar-Hillel et al. 1961Bar-Hillel, Yehoshua, Micha Perles & Eliyahu Shamir 1961 “On Formal Properties of Simple Phrase Structure Grammars”. Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14.143–172. Reprinted with revisions in Bar-Hillel (1964), 116–150.Bar-Hillel, Yehoshua, Micha Perles & Eliyahu Shamir 1961 “On Formal Properties of Simple Phrase Structure Grammars”. Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung 141.143–172. Reprinted with revisions in Bar-Hillel (1964), 116–150., and it seems likely that he picked up the reference to Post 1946Post, Emil L. 1946 “A Variant of a Recursively Unsolvable Problem”. Bulletin of the American Mathematical Society 524.264–268. Reproduced in Davis (1994b: 495–500). Post, Emil L. 1946 “A Variant of a Recursively Unsolvable Problem”. Bulletin of the American Mathematical Society 5241.264–268. Reproduced in Davis (1994b: 495–500). from them.)

• On two occasions when speaking informally at conferences Chomsky acknowledged the influence of Post without references, mentioning ‘the approach to recursive function theory based on ideas of Emil Post’ (conference in Israel, April 1988; see Chomsky 1991Chomsky, Noam 1991 “Linguistics and Adjacent Fields: A personal view”. The Chomskyan Turn ed. by Asa Kasher, 3–25. Oxford: Blackwell.Chomsky, Noam 1991 “Linguistics and Adjacent Fields: A personal view”. The Chomskyan Turn ed. by Asa Kasher, 3–25. Oxford: Blackwell.: 21) and ‘One of the notations [for recursive functions], by a logician named Emil Post’ (conference in Spain, June 2006; see Piattelli-Palmarini et al. (eds.): 389).1515.A note was added to Chomsky’s remark in the latter case, saying, ‘Post (1943)Post, Emil L. 1943 “Formal Reductions of the General Combinatory Decision Problem”. American Journal of Mathematics 65:2.197–215. Reproduced in Davis (1994b: 442–460). Post, Emil L. 1943 “Formal Reductions of the General Combinatory Decision Problem”. American Journal of Mathematics 65:2.197–215. Reproduced in Davis (1994b: 442–460). . (Editors’ note)’. But it was the volume editors who put that in, not Chomsky. The editors may have noted that by 2009 Post’s papers and Chomsky’s odd reluctance to cite them had been mentioned in two papers by Pullum and Scholz (2001Pullum, Geoffrey K. & Barbara C. Scholz 2001 “On the Distinction between Model-Theoretic and Generative-Enumerative Syntactic Frameworks”. Logical Aspects of Computational Linguistics: 4th International Conference, number 2099 in Lecture Notes in Artificial Intelligence, ed. by Philippe de Groote, Glyn Morrill & Christian Retoré, 17–43. Berlin / New York: Springer. Pullum, Geoffrey K. & Barbara C. Scholz 2001 “On the Distinction between Model-Theoretic and Generative-Enumerative Syntactic Frameworks”. Logical Aspects of Computational Linguistics: 4th International Conference, number 2099 in Lecture Notes in Artificial Intelligence, ed. by Philippe de Groote, Glyn Morrill & Christian Retoré, 17–43. Berlin / New York: Springer. , 2005Pullum, Geoffrey K. & Barbara C. Scholz 2005 “Contrasting Applications of Logic in Natural Language Syntactic Description”. Proceedings of the 13th International Congress of Logic, Methodology and Philosophy of Science ed. by Petr Hájek, Luis Valdés-Villanueva & Dag Westerståhl, 481–503. London: KCL Publications.Pullum, Geoffrey K. & Barbara C. Scholz 2005 “Contrasting Applications of Logic in Natural Language Syntactic Description”. Proceedings of the 13th International Congress of Logic, Methodology and Philosophy of Science ed. by Petr Hájek, Luis Valdés-Villanueva & Dag Westerståhl, 481–503. London: KCL Publications.) and in Scholz and Pullum (2007)Scholz, Barbara C. & Geoffrey K. Pullum 2007 “Tracking the Origins of Generative Grammar”. Journal of Linguistics 43.701–723. Scholz, Barbara C. & Geoffrey K. Pullum 2007 “Tracking the Origins of Generative Grammar”. Journal of Linguistics 431.701–723. .

• The book Why Only Us (Berwick and Chomsky 2016Berwick, Robert & Noam Chomsky 2016 Why Only Us? Language and evolution. Cambridge, MA: MIT Press. Berwick, Robert & Noam Chomsky 2016 Why Only Us? Language and evolution. Cambridge, MA: MIT Press. ) has a brief reference (p. 70) to ‘one of the several equivalent formulations of the mathematical theory of recursive procedures — Emil Post’s rewriting systems’, but with no citation.

One other very close approach to exemplifying production systems in Post’s form should be mentioned, though it does not mention Post’s name at all. In the introduction to the formal linguistics that Chomsky coauthored with George Miller for the Handbook of Mathematical Psychology (Chomsky and Miller 1963Chomsky, Noam & George A. Miller 1963 “Introduction to the Formal Analysis of Natural Languages”. eds., Handbook of Mathematical Psychology, Volume II, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 269–322. New York: Wiley.Chomsky, Noam & George A. Miller 1963 “Introduction to the Formal Analysis of Natural Languages”. eds., Handbook of Mathematical Psychology, Volume II1, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 269–322. New York: Wiley.: 284), the term ‘grammar’ is introduced thus:

… by a grammar we mean a set of rules that (in particular) recursively specify the sentences of a language. In general, each of the rules we need will be of the form

ϕ ₁,...,ϕ _n→ϕ _n+1,

(5)

where each of the ϕ_i is a structure of some sort and where the relation → is to be interpreted as expressing the fact that if our process of recursive specification generates the structures ϕ ₁,...,ϕ_n then it also generates [t]he structure ϕ _n+1.

This is unmistakably an allusion to canonical production systems: the ϕ ₁, . . . , ϕ_n before the arrow are the premise templates; the single ϕ _n+1 after it is the conclusion template. Yet there is no mention of Post’s name, nor a citation of the relevant paper, Reductions.

Curiously, then, Chomsky has never, in all of his voluminous work, mentioned either of the two key papers of Post’s that introduced production systems and demonstrated their expressive power: Reductions and Unsolvability. That is puzzling. It has led at least two 21st-century historians of linguistics to express opinions that might be interpreted as implying ethical criticism.

First, in some critical remarks about Tomalin (2006)Tomalin, Marcus 2006 Linguistics and the Formal Sciences: The origins of generative grammar. Cambridge: Cambridge University Press. Tomalin, Marcus 2006 Linguistics and the Formal Sciences: The origins of generative grammar. Cambridge: Cambridge University Press. , Seuren (2009Seuren, Pieter A. M. 2009 “Concerning the Roots of Transformational Generative Grammar”. Historiographia Linguistica 36:1.97–115. Seuren, Pieter A. M. 2009 “Concerning the Roots of Transformational Generative Grammar”. Historiographia Linguistica 36:1.97–115. : 101) comments that ‘Chomsky has consistently failed to point out to his readers that he owes his notion of TGG to Post (the only reference to Post I am aware of is in the hardly accessible Chomsky 1959a, in a footnote that attributes the term generate to Post).’ Seuren has overlooked one or two cases that I pointed out above, but it is true that Chomsky never pointed to Reductions or Unsolvability to make the point that the source of his rewriting systems may be found there. Seuren also pointed out to me in a personal communication (March 2019) that Beth (1963Beth, Evert W. 1963 “Konstanten van het wiskundige denken [constants in mathematical thinking]”. Mededelingen der Koninklijke Nederlandse Akademie van Wetenschappen: Afdeling Letterkunde, Nieuwe Reeks 26:7.231–256.Beth, Evert W. 1963 “Konstanten van het wiskundige denken [constants in mathematical thinking]”. Mededelingen der Koninklijke Nederlandse Akademie van Wetenschappen: Afdeling Letterkunde, Nieuwe Reeks 26:7.231–256., esp. pp. 240–241 and 248–249) states explicitly that he sees Chomsky’s transformational-generative grammar as deriving directly from Post’s work on production systems. Beth clearly alludes to Reductions, but cites (p. 241, Footnote 14) only a secondary source, Rosenbloom (1950)Rosenbloom, Paul 1950 The Elements of Mathematical Logic. New York: Dover.Rosenbloom, Paul 1950 The Elements of Mathematical Logic. New York: Dover., to be discussed further below (§ 5.4).

Second, Nevin (2009)Nevin, Bruce E. 2009 “More concerning the Roots of Transformational Generative Grammar”. Historiographia Linguistica 36:2/3.459–479. Nevin, Bruce E. 2009 “More concerning the Roots of Transformational Generative Grammar”. Historiographia Linguistica 36:2/3.459–479. refers to Post as ‘the actual though largely unacknowledged inventor (e.g., Post 1943Post, Emil L. 1943 “Formal Reductions of the General Combinatory Decision Problem”. American Journal of Mathematics 65:2.197–215. Reproduced in Davis (1994b: 442–460). Post, Emil L. 1943 “Formal Reductions of the General Combinatory Decision Problem”. American Journal of Mathematics 65:2.197–215. Reproduced in Davis (1994b: 442–460). ) of the rewrite systems that Chomsky adapted for his formalization of immediate constituent analysis as Phrase Structure Grammar, and the source of the now familiar and, as it were, trademarked, terms “generate” and “generative”.’1616.Nevin appears to make a small error here: I don’t think I have seen the term ‘generative’ anywhere in Post’s work; that is Chomsky’s coinage. And in a later work he speaks of Chomsky’s use of rewriting systems as having been ‘adapted (without credit) from Post (1943)Post, Emil L. 1943 “Formal Reductions of the General Combinatory Decision Problem”. American Journal of Mathematics 65:2.197–215. Reproduced in Davis (1994b: 442–460). Post, Emil L. 1943 “Formal Reductions of the General Combinatory Decision Problem”. American Journal of Mathematics 65:2.197–215. Reproduced in Davis (1994b: 442–460). ’ to express the morphophonemic statements in his MA thesis (Nevin 2010Nevin, Bruce E. 2010 “Noam and Zellig”. Chomskyan (R)evolutions ed. by Douglas A. Kibbee, 103–168. Amsterdam: John Benjamins. Nevin, Bruce E. 2010 “Noam and Zellig”. Chomskyan (R)evolutions ed. by Douglas A. Kibbee, 103–168. Amsterdam: John Benjamins. : 119, fn. 34). Nevin cites Reductions in this connection.

These are not phrased as accusations of deliberate concealment. The statements Seuren and Nevin make are basically factual, and verifiable from the literature. But if some were to discern a hint of disapproval, it might be because of a connection to the fact that Chomsky has often eschewed citation of clearly relevant work by specific linguists whose work he chooses not to promote. For example, I can find no references by Chomsky to much-cited syntacticians like Charles Fillmore and James McCawley since the 1960s. Chomsky’s references to his mentor Zellig Harris also fell away to absolutely minimal levels after his very early work. And there are more extreme cases of citation denial: unless I have missed something, in his entire career he never cited any work by the philosopher of linguistics Esa Itkonen, or linguists like John Joseph, William Labov, Geoffrey Sampson, or Pieter Seuren, all of whom published thoughtful criticisms of his approach. Despite his enormously wide range of works read and referenced, he appears in some cases to be implementing something like an excommunication.

One might say ‘So what?’, of course. And the answer to that has to do with the fact that Chomsky is the most influential and important linguist of the past century by a huge margin — probably the most famous and revered linguist who ever lived — and has enthusiasts in the profession who follow his practices closely, so it makes a real difference to linguists’ careers and livelihoods whether he acknowledges their work or treats it as if it were tabooed.

It is also well known that Chomsky has sometimes taken over ideas from others and presented them as his own insights when the earlier espousals were by linguists he prefers not to engage with in detail; see e.g. the list in Pullum (1989Pullum, Geoffrey K. 1989 “Prospects for Generative Grammar in the 1990s”. Proceedings of the Western Conference on Linguistics [WECOL 89], Volume 2, ed.by Frederick H. Brengelman, Vida Samiian & Wendy Wilkins, 257–276. California State University, Fresno: Department of Linguistics.Pullum, Geoffrey K. 1989 “Prospects for Generative Grammar in the 1990s”. Proceedings of the Western Conference on Linguistics [WECOL 89], Volume 2, ed.by Frederick H. Brengelman, Vida Samiian & Wendy Wilkins, 257–276. California State University, Fresno: Department of Linguistics.: 264–266) of ideas that Chomsky adapted from the generative semantics literature without acknowledement during the 1980s, or the copious evidence of plundering that literature supplied by Randy Allen Harris in a section entitled ‘The Legacy of Generative Semantics 1: The Right of Salvage’ (Harris 2021Harris, Randy Allen 2021 The Linguistics Wars: Chomsky, Lakoff, and the battle over deep structure. New York: Oxford University Press, second ed.. Harris, Randy Allen 2021 The Linguistics Wars: Chomsky, Lakoff, and the battle over deep structure. New York: Oxford University Press, second ed.. : 333–341).

There is a difference, however, between practices of this sort and active concealment of a source. Chomsky’s practices might be better seen, I think, as stemming from his preference for an implicit ‘no comment’ when challenged by negative critics in print, and his preference for presenting ideas in his own terms rather than reanimating the ‘linguistics wars’ and wrangling with earlier ideas differently framed. One might disapprove of such a policy, but it is different from deliberate suppression of key ideas or their sources. And it should be noted that wherever Chomsky has noticed relevant insights stemming from other fields — philosophy, psychology, biology, artificial intelligence — his practice has been to explore their writings extensively, with full citation. And that is especially true if they are no longer living. He has discussed scores of transdisciplinary predecessors: philosophers and logicians (Descartes, Frege, Grice, Hume, Kant, Leibniz, Locke, Mill, Peirce, Plato, Quine, Rousseau, Russell, Wittgenstein), psychologists and ethologists (Freud, Jung, Lashley, Lorenz, Skinner, Thorpe), and other scientists (Galileo, Haldane, Humboldt, Lévi-Strauss, Luria, Priestley…). Merely glancing at the name indexes in a few of Chomsky’s books should remind us that he was always extraordinarily energetic in citing intellectual antecedents and relating linguistics to other fields. (It is true that, as pointed out by Joseph (1990Joseph, John E. 1990 “Ideologizing Saussure: Bloomfield’s and Chomsky’s readings of the Cours de linquistique générale ”. Ideologies of Language ed. by John E. Joseph & Talbot J. Taylor, 51–78. London: Routledge.Joseph, John E. 1990 “Ideologizing Saussure: Bloomfield’s and Chomsky’s readings of the Cours de linquistique générale”. Ideologies of Language ed. by John E. Joseph & Talbot J. Taylor, 51–78. London: Routledge., 2002Joseph, John E. 2002 From Whitney to Chomsky. Amsterdam: John Benjamins. Joseph, John E. 2002 From Whitney to Chomsky. Amsterdam: John Benjamins. , Chapter 6), Chomsky has shifted over time in his allegiance from one to another of the antecedents he discusses; but there can be no doubt about his interest in discussing them.)

Given that Post was a mathematician and logician, not a linguist, and was dead before Chomsky published anything on generative grammars,1717.Tragically, Post had a heart attack in 1954 just after a high-voltage electroshock treatment which at the time was thought to be appropriate for his bipolar disorder. he is not in any way representative of the contemporary critics within linguistics that Chomsky frequently prefers to leave uncited even when adopting their ideas. Rather, Post is exactly the kind of figure we might expect Chomsky to claim as an academic ancestor.

5.3Chomsky’s own account of his learning about Post

It would be natural to ask what acquaintances or correspondents of Chomsky’s have known him say about his knowledge of Post’s work. And at least three people have provided relevant information.

A vague hint comes from Yehoshua Bar-Hillel (1915–1975), who became a friend of Chomsky’s in the fall of 1951 and greatly admired him (see Bar-Hillel 1964Bar-Hillel, Yehoshua 1964 Language and Information: Selected essays on their theory and application. Reading, MA: Addison-Wesley.Bar-Hillel, Yehoshua 1964 Language and Information: Selected essays on their theory and application. Reading, MA: Addison-Wesley.: 15–16). Bar-Hillel was certainly familiar with Post’s work. On April 28, 1951, he had presented a paper at a one-session meeting of the Association for Symbolic Logic at Columbia University in New York; the next paper in the session (by William W. Boone) was entirely devoted to developing ideas of Post’s, and the paper immediately after that was presented by Post himself (for the program of the meeting, see Journal of Symbolic Logic 16:3, 236–240). And in his 1964 book Language and Information (1964: 103) he notes that the approach to syntax of Chomsky (1956)Chomsky, Noam 1956 “Three Models for the Description of Language”. I.R.E. Transactions on Information Theory IT-2.113–123. Substantially revised version published in Readings in Mathematical Psychology, Volume II ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 105–124. New York: John Wiley & Sons 1965 Chomsky, Noam 1956 “Three Models for the Description of Language”. I.R.E. Transactions on Information Theory IT-21.113–123. Substantially revised version published in Readings in Mathematical Psychology, Volume II ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 105–124. New York: John Wiley & Sons 1965  ‘was to look on grammar as a device for the generation (or production) of the set of grammatical sentences, rather than as a device for the recognition of given strings as sentences’, and comments that ‘This approach is the standard one for the combinatorial systems conceived much earlier by Post’ (he cites Post 1936Post, Emil L. 1936 “Finite Combinatory Processes — Formulation 1”. Journal of Symbolic Logic 1:3.103–105. Reproduced in Davis (1965: 288–291) and in Davis (1994b: 103–105). Post, Emil L. 1936 “Finite Combinatory Processes — Formulation 1”. Journal of Symbolic Logic 1:3.103–105. Reproduced in Davis (1965: 288–291) and in Davis (1994b: 103–105). ), and then he adds: ‘though Chomsky seems to have become aware of the proximity of his ideas with those of Post only at a later stage of his work.’ This presumably means later than 1956. How much later is not clear. We do not know whether Chomsky and Bar-Hillel discussed Post’s work when they met and became friends in the fall of 1951. Apparently not.

More recent details come from a short biographical piece about Post by Allyn Jackson (2018)Jackson, Allyn 2018 “Emil Post: Psychological fidelity”. Inference: International Review of Science 4:2. Online at https://​inference​-review​.com​/article​/psychological​-fidelityJackson, Allyn 2018 “Emil Post: Psychological fidelity”. Inference: International Review of Science 4:2. Online at https://​inference​-review​.com​/article​/psychological​-fidelity, an article which is unfortunately inaccurate on many details regarding logic and computation. She states:

The first to apply Post production systems was Noam Chomsky, who found in them just the right structures for his revolutionary theory of the grammars of natural languages. Chomsky carried out this work in the 1950s, but he never met Post, who died in 1954. ‘Post is a much undervalued figure,’ Chomsky said in an email message to me. ‘When I was a student, including 4 fellowship years at Harvard (1951–1955, mostly philosophy, logic), I never heard his name.’ Chomsky learned of Post’s work from Paul Rosenbloom’s The Elements of Mathematical Logic, published in 1950, and from the work of Davis.

It is somewhat surprising to hear that Chomsky never heard Post’s name around Harvard, given that Chomsky sat in on Willard Quine’s logic course at Harvard between 1951 and 1955 when he was at Harvard’s Society of Junior Fellows. Quine does cite Post in his textbook Mathematical Logic (1940Quine, Willard Van Orman 1940 Mathematical Logic. New York, NY: W. W. Norton.Quine, Willard Van Orman 1940 Mathematical Logic. New York, NY: W. W. Norton.), but a closer look reveals that it contains only three occurrences of Post’s name, all of them brief references to Post (1921)Post, Emil L. 1921 “Introduction to a General Theory of Elementary Propositions”. American Journal of Mathematics 43:3.163–185. Reprinted in van Heijenoort (1967: 264–283) and reproduced in Davis (1994b: 21–43). Post, Emil L. 1921 “Introduction to a General Theory of Elementary Propositions”. American Journal of Mathematics 43:3.163–185. Reprinted in van Heijenoort (19671: 264–283) and reproduced in Davis (1994b: 21–43). in end-of-chapter bibliographical notes. There is no hint of anything about the production systems that Post developed after 1921, and it is quite possible that Quine never discussed Post at all in his lectures.

One other person who corresponded with Chomsky about Emil Post is Liesbeth De Mol, a historian of computer science, who told me (personal communication, 27 February 2019) that she had asked Chomsky by email about Post’s influence on his work, and in his reply he said that in the 1950s ‘Post systems were little known, apart from Martin Davis’s book, where I learned about them, then checked some of the papers.’

The book Chomsky alludes to would almost certainly have been Computability and Unsolvability (Davis 1958Davis, Martin ed. 1958 Computability and Unsolvability. New York: McGraw-Hill.Davis, Martin ed. 1958 Computability and Unsolvability. New York: McGraw-Hill.), the first textbook devoted to computability theory. So Chomsky is saying he did not learn about production systems until the year before he published his 1959 paper. He did not specify which papers he checked after reading Davis’s book, but one of them has to have been Post (1944)Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). , which he cites.

5.4The Rosenbloom textbook

Taking Chomsky at his word about not having known Post’s work until 1958, however, raises a problem about the role of The Elements of Mathematical Logic, a textbook published by Paul Rosenbloom in 1950Rosenbloom, Paul 1950 The Elements of Mathematical Logic. New York: Dover.Rosenbloom, Paul 1950 The Elements of Mathematical Logic. New York: Dover.. Jackson’s mention of Rosenbloom probably stems from the remark by Urquhart (2009Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier.Urquhart, Alasdair 2009 “Emil Post”. The Handbook of the History of Logic, Volume 5 ed. by Dov Gabbay & John Woods. 617–666. Amsterdam: Elsevier.: 471) that Chomsky ‘seems to have known of these [Post’s] ideas indirectly through the unusual textbook of Paul Rosenbloom [Rosenbloom, 1950Rosenbloom, Paul 1950 The Elements of Mathematical Logic. New York: Dover.Rosenbloom, Paul 1950 The Elements of Mathematical Logic. New York: Dover.], in which Post’s production systems are given a starring role, particularly in the last chapter.’

Chomsky almost certainly learned something about Post, or heard him mentioned, at the University of Pennsylvania between 1947 and 1951. Bruce Nevin (personal communication) tells me that he definitely recalls that when he was an undergraduate in that department (circa 1966) Henry Hoenigswald mentioned Post to him in some relevant context. And we can definitely be sure that Chomsky knew the Rosenbloom book some time between 1947 and 1951, when he was a student there, because the Polish-American philosopher, logician, and linguist Henry Hiż (1917–2006) used it as a text in a class that Chomsky took at the University of Pennsylvania (Michael Gottfried, personal communication via Bruce Nevin, 17 December 2018). Furthermore, Chomsky cites Rosenbloom’s book four times in his early works:

• He cites it in his PhD dissertation (1955: xiii).

• He cites it in the much longer monograph of which it was a part, The Logical Structure of Linguistic Theory (1955–56, henceforth LSLT); the citation is in the chapter headed ‘Linguistic levels’, appearing in the 1956 typescript available at http://​alpha​-leonis​.lids​.mit​.edu​/chomsky​/chomsky​_thesis​.pdf in Chapter II on p. II–1^fn, and in the 1975 print version in Chapter III, p. 105.

• He mentions the book again in ‘Three models for the description of language’ (Chomsky 1956Chomsky, Noam 1956 “Three Models for the Description of Language”. I.R.E. Transactions on Information Theory IT-2.113–123. Substantially revised version published in Readings in Mathematical Psychology, Volume II ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 105–124. New York: John Wiley & Sons 1965 Chomsky, Noam 1956 “Three Models for the Description of Language”. I.R.E. Transactions on Information Theory IT-21.113–123. Substantially revised version published in Readings in Mathematical Psychology, Volume II ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter, 105–124. New York: John Wiley & Sons 1965 : 12, fn 2).

• And he cites it once more in Aspects of the Theory of Syntax (Chomsky 1965Chomsky, Noam 1965 Aspects of the Theory of Syntax. Cambridge, MA: MIT Press.Chomsky, Noam 1965 Aspects of the Theory of Syntax. Cambridge, MA: MIT Press.: 222, n. 2).

There is a strange aspect to these citations, however. In each case, Chomsky cites Rosenbloom merely as a source for the basic concepts and terminology of concatenation algebras; mostly he cites just Appendix 2 of the book. This is especially odd given that he makes virtually no use of the notations or axioms found in that appendix (though possibly his practice of using the arrow ‘→’ for Post’s ‘produce’ came from Rosenbloom).

What makes Rosenbloom’s book so significant is the existence of two highly significant passages that Chomsky has never mentioned. Although Post never considered applying production systems to human languages, it seems that Rosenbloom did. He suggests first that if a logician tried to ‘construct the English language by taking as the alphabet the strings of letters already classified as words’, the approach would face grave problems:

As in all natural languages, including Esperanto, the rules of word and sentence formation in English are so complicated and full of irregularities and exceptions that it is almost impossible to get a general view of the structure of the language.

That passage (Rosenbloom 1950Rosenbloom, Paul 1950 The Elements of Mathematical Logic. New York: Dover.Rosenbloom, Paul 1950 The Elements of Mathematical Logic. New York: Dover.: 153) is quoted in the first edition of F. J. Newmeyer’s history of generative grammar (1980Newmeyer, Frederick J. 1980 Linguistic Theory in America. New York, NY: Academic Press. First edition 1980; second edition 1986.Newmeyer, Frederick J. 1980 Linguistic Theory in America. New York, NY: Academic Press. First edition 1980; second edition 1986.: 36), which is where I learned of it, but it was omitted from Newmeyer’s second edition (1986) to make room for material that was to be added. What Newmeyer never mentioned, though, is that ten pages later (162–163), after a careful introduction to canonical production systems and the content of Reductions, Rosenbloom starts sounding more optimistic, and makes this important and prescient proposal about Post’s canonical production systems:

With this tool at our disposal we can explain simply and elegantly many important mathematical and logical notions. One might also expect that many concepts in linguistics which have resisted all attempts up to now at clear and general formulation may now be treated with the same lucidity and rigor which has made mathematics a model for other sciences. The wealth of detail and the manifold irregularities of natural languages have often obfuscated the simple general principles underlying linguistic phenomena.

Rosenbloom is explicitly proposing that Post’s systems could be deployed within linguistics as grammars for human languages, and confidently predicting successful discovery of ‘simple general principles underlying linguistic phenomena.’

It would be hard for an interested reader, especially one with a primary interest in linguistics, to read or even just skim Rosenbloom without noticing that passage, and the many respectful references to Post in Chapter IV, ‘The General Syntax of Language’. Chomsky could hardly have overlooked these if he read the text for the course he took with Hiż.

Even here, though, there is room for doubt about a more specific point: whether Rosenbloom’s book would have led Chomsky to acquaint himself with the text of Post’s most relevant papers, Reductions and Unsolvability. Rosenbloom’s book does, as Urquhart says, give canonical production systems ‘a starring role’; but the book has a rather odd feature which might lessen the chances of a reader going back to its primary sources. Its section headed ‘Bibliographical and other remarks’ (194–208) gives very few explicit bibliographical references. Discovering the identity of most of the works cited involves decoding certain space-saving numerical codes explained nearly two hundred pages earlier by a key on p. iv at the end of the introduction. These codes use both Roman and Arabic numerals in ways that are by no means intuitive or self-explanatory. For example, the codes ‘III2’, ‘[III]2’, and ‘[3]2’ would mean three totally different things in Rosenbloom’s bibliographical code:

• ‘III2’ would refer to Section 2 of Chapter 3 of Rosenbloom’s book itself.

• ‘[III]2’ would refer to a paper that either begins on page 2 of volume 3 of the Journal of Symbolic Logic or is summarized by an abstract that begins on that page.

• ‘[3]2’ would refer to the second paper by the third author in the bibliography of symbolic logic that Alonzo Church published in pages 121–216 of the Journal of Symbolic Logic vol. 1, no. 4 (1936).

So back in 1950, 45 years before JSTOR, if you wanted to find out what Rosenbloom means when he mentions (on p. 206) Post’s ‘profound and beautiful paper [X]18’, you would first have to recognize that ‘X’ is a roman numeral, and is in square brackets, and therefore refers to a volume of JSL. Then you’d have to go over to the library, find volume 10, and look in it to see which paper by Post either (i) begins on page 18 or (ii) is summarized by an abstract that begins on page 18. Certainly, a determined student would be able to find the relevant papers by Post by following Rosenbloom’s cryptic codes, but one can imagine a student being discouraged by such a procedure and not bothering to track down the primary sources, especially if his main interests were in matters like Hebrew morphophonemics.

How much Chomsky knew about Reductions and Unsolvability, and by exactly when, therefore remains very difficult to resolve. But it matters, because we are not talking about mere distant historical echoes. Chomsky’s early generative grammars (from 1955 to about 1964) really are just Post production systems, though stated differently and less rigorously. It is fairly clear that by 1951 Rosenbloom’s detailed treatment of Post’s work, in which he suggested applying it to linguistics, had been brought to Chomsky’s attention. And it is also clear that in later years he must have taken note not only of Davis (1958)Davis, Martin ed. 1958 Computability and Unsolvability. New York: McGraw-Hill.Davis, Martin ed. 1958 Computability and Unsolvability. New York: McGraw-Hill. but also later works on computability and formal systems such as Rogers (1967)Rogers, Hartley 1967 Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press.Rogers, Hartley 1967 Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press.,1818.Chomsky (1963Chomsky, Noam 1963 “Formal Properties of Grammars”. Handbook of Mathematical Psychology, Volume II, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter 323–418. New York: Wiley.Chomsky, Noam 1963 “Formal Properties of Grammars”. Handbook of Mathematical Psychology, Volume II1, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter 323–418. New York: Wiley.: 354) cites a 1961Chomsky, Noam 1961 “On the notion ‘rule of grammar’.” Proceedings of the Twelfth Symposium in Applied Mathematics, 6–24. Providence, RI: American Mathematical Society. Reprinted in The Structure of Language: Readings in the philosophy of language ed. by Jerry A. Fodor & Jerrold J. Katz, 155–210. Englewood Cliffs, NJ: Prentice-Hall. Chomsky, Noam 1961 “On the notion ‘rule of grammar’.” Proceedings of the Twelfth Symposium in Applied Mathematics, 6–24. Providence, RI: American Mathematical Society. Reprinted in The Structure of Language: Readings in the philosophy of language ed. by Jerry A. Fodor & Jerrold J. Katz, 155–210. Englewood Cliffs, NJ: Prentice-Hall. manuscript version of Rogers’ book, which was written at MIT. Minsky (1967)Minsky, Marvin L. 1967 Computation: Finite and infinite machines. Englwood Cliffs, NJ: Prentice-Hall.Minsky, Marvin L. 1967 Computation: Finite and infinite machines. Englwood Cliffs, NJ: Prentice-Hall., and Gross and Lentin (1970)Gross, Maurice & André Lentin 1970 Introduction to Formal Grammars. London: George Allen & Unwin. Translated by Morris Salkoff. Gross, Maurice & André Lentin 1970 Introduction to Formal Grammars. London: George Allen & Unwin. Translated by Morris Salkoff. , all three of which feature theorems about Post production systems. Yet still he never mentions Reductions or Unsolvability.

5.5The puzzle of Chomsky’s blind spot, and its solution

One point of common sense strengthens my belief that Seuren (2009)Seuren, Pieter A. M. 2009 “Concerning the Roots of Transformational Generative Grammar”. Historiographia Linguistica 36:1.97–115. Seuren, Pieter A. M. 2009 “Concerning the Roots of Transformational Generative Grammar”. Historiographia Linguistica 36:1.97–115. and Nevin (2010)Nevin, Bruce E. 2010 “Noam and Zellig”. Chomskyan (R)evolutions ed. by Douglas A. Kibbee, 103–168. Amsterdam: John Benjamins. Nevin, Bruce E. 2010 “Noam and Zellig”. Chomskyan (R)evolutions ed. by Douglas A. Kibbee, 103–168. Amsterdam: John Benjamins. overstate the case as regards Chomsky’s debt to Post’s papers. Surely anyone trying to appropriate the work of an earlier scholar without acknowledgment would realize that their best course was never to mention that scholar’s name at all. The maximum plausible deniability would be obtained by appearing to be completely ignorant of the appropriated work. If Post was hardly mentioned by anyone during the 1950s, even in logic classes at Harvard, Chomsky could readily have claimed that he had no knowledge of Post’s work at all. But he did not adopt a policy of zero mentions. Instead, he deliberately and repeatedly gave pointers to Post’s contributions and relevance over more than half a century. Why would he ruin his supposed cover-up like that?

It seems to me that the documentable facts force us toward a completely different conclusion. Far from having tried to keep Post’s name out of the picture, Chomsky appears to be literally the only linguist in the entire 20th century who ever cited Post at all. Even in Arnold Zwicky’s mathematical study of how rewriting systems can capture number-theoretic predicates (Zwicky 1963Zwicky, Arnold M. 1963 “Grammars of Number Theory: Some examples”. Working Paper W-6671, MITRE Corporation, Bedford, MA. Online at: https://​web​.stanford​.edu​/∼zwicky​/grammars​-of​-number​-theory​.pdfZwicky, Arnold M. 1963 “Grammars of Number Theory: Some examples”. Working Paper W-6671, MITRE Corporation, Bedford, MA. Online at: https://​web​.stanford​.edu​/∼zwicky​/grammars​-of​-number​-theory​.pdf) there is no mention of Post, which is truly surprising, since Zwicky’s project is so closely related to what Post (1944)Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). was doing: studying the mathematical properties of sets of positive integers through the character of rewriting systems that generate them, representing integers in unary notation and so on). The general ideas Post had raised seem to have been under discussion in the 1960s at and around MIT, but apparently linguists had no acquaintance with his most crucially relevant papers.

Perhaps the most surprising point of all about the 20th-century linguistics literature is that there are no citations of Post’s key papers even in works on mathematical linguistics. Searching Hockett (1966)Hockett, Charles F. 1966 “Language, Mathematics and Linguistics. Current Trends in Linguistics: Volume 3, theoretical foundations, 155–304. The Hague: Mouton. Republished as a monograph by Mouton, The Hague 1967.Hockett, Charles F. 1966 “Language, Mathematics and Linguistics. Current Trends in Linguistics: Volume 3, theoretical foundations, 155–304. The Hague: Mouton. Republished as a monograph by Mouton, The Hague 1967., Wall (1972)Wall, Robert 1972 Introduction to Mathematical Linguistics. Englewood Cliffs, NJ: Prentice-Hall.Wall, Robert 1972 Introduction to Mathematical Linguistics. Englewood Cliffs, NJ: Prentice-Hall., Kimball (1973)Kimball, John 1973 The Formal Theory of Grammar. Englewood Cliffs, NJ: Prentice-Hall.Kimball, John 1973 The Formal Theory of Grammar. Englewood Cliffs, NJ: Prentice-Hall., Levelt (1974Levelt, W. J. M. 1974 Formal Grammars in Linguistics and Psycholinguistics. The Hague: Mouton. 4 volumes; republished in one volume as Levelt (2008).Levelt, W. J. M. 1974 Formal Grammars in Linguistics and Psycholinguistics. The Hague: Mouton. 41 volumes; republished in one volume as Levelt (2008)., 2008Levelt, W. J. M. 2008 Formal Grammars in Linguistics and Psycholinguistics. Amsterdam: John Benjamins. Levelt, W. J. M. 2008 Formal Grammars in Linguistics and Psycholinguistics. Amsterdam: John Benjamins. ), Partee (1978)Partee, Barbara Hall 1978 Fundamentals of Mathematics for Linguistics. Dordrecht: D. Reidel.Partee, Barbara Hall 1978 Fundamentals of Mathematics for Linguistics. Dordrecht: D. Reidel., or Partee et al. (1993)Partee, Barbara Hall, Alice ter Meulen & Robert E. Wall 1993 Mathematical Methods in Linguistics. Dordrecht: Kluwer. Partee, Barbara Hall, Alice ter Meulen & Robert E. Wall 1993 Mathematical Methods in Linguistics. Dordrecht: Kluwer. yields not a single citation of a paper by Post.

Kimball (1973Kimball, John 1973 The Formal Theory of Grammar. Englewood Cliffs, NJ: Prentice-Hall.Kimball, John 1973 The Formal Theory of Grammar. Englewood Cliffs, NJ: Prentice-Hall.: 85) does note that ‘Phrase structure grammars are species of systems developed by E. Post, called Post-systems, for the purpose of modeling deductions in formalized systems’, but gives no reference. Partee (1978Partee, Barbara Hall 1978 Fundamentals of Mathematics for Linguistics. Dordrecht: D. Reidel.Partee, Barbara Hall 1978 Fundamentals of Mathematics for Linguistics. Dordrecht: D. Reidel.: 168) remarks that ‘Post’s production systems … were quite similar to what Chomsky later called string rewriting systems’, and Partee et al. (1993Partee, Barbara Hall, Alice ter Meulen & Robert E. Wall 1993 Mathematical Methods in Linguistics. Dordrecht: Kluwer. Partee, Barbara Hall, Alice ter Meulen & Robert E. Wall 1993 Mathematical Methods in Linguistics. Dordrecht: Kluwer. : 516) mentions ‘Kleene, Post, Markov, Church, and others’ in connection with the Church–Turing thesis, but again, no papers are cited.

Even the unusually abstract and mathematical book by Gross and Lentin (1970)Gross, Maurice & André Lentin 1970 Introduction to Formal Grammars. London: George Allen & Unwin. Translated by Morris Salkoff. Gross, Maurice & André Lentin 1970 Introduction to Formal Grammars. London: George Allen & Unwin. Translated by Morris Salkoff. , which does mentions Post’s correspondence problem and follows Chomsky (1963)Chomsky, Noam 1963 “Formal Properties of Grammars”. Handbook of Mathematical Psychology, Volume II, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter 323–418. New York: Wiley.Chomsky, Noam 1963 “Formal Properties of Grammars”. Handbook of Mathematical Psychology, Volume II1, ed. by R. Duncan Luce, Robert R. Bush & Eugene Galanter 323–418. New York: Wiley. in citing Post (1946)Post, Emil L. 1946 “A Variant of a Recursively Unsolvable Problem”. Bulletin of the American Mathematical Society 524.264–268. Reproduced in Davis (1994b: 495–500). Post, Emil L. 1946 “A Variant of a Recursively Unsolvable Problem”. Bulletin of the American Mathematical Society 5241.264–268. Reproduced in Davis (1994b: 495–500). , does not cite Reductions or Unsolvability.1919.Two almost-exceptions to my claims here have been suggested to me, but they really only underline my point. Bart Karstens pointed out some eccentric remarks about variability, meaning, and creativity in Jakobson (1969Jakobson, Roman 1969 “Linguistics in its Relation to Other Sciences. Proceedings of the 10th International Congress of Linguists, 75–111. Bucharest: Éditions de l’Académie de la République Socialiste de Roumanie. Page reference is to the reprinting in Jakobson’s, Selected Writings, II: Word and Language (The Hague: Mouton 1971), 655–708.Jakobson, Roman 1969 “Linguistics in its Relation to Other Sciences. Proceedings of the 10th International Congress of Linguists, 75–111. Bucharest: Éditions de l’Académie de la République Socialiste de Roumanie. Page reference is to the reprinting in Jakobson’s, Selected Writings, II: Word and Language (The Hague: Mouton 1971), 655–708.: 659) quotes four stray phrases (out of context and out of sequence) from some diary fragments in Post (1941[1965])Post, Emil L. 1941[1965] “Absolutely Undecidable Problems and Relatively Undecidable Propositions — Account of an Anticipation”. Rejected by American Journal of Mathematics in 1941; posthumously published in Davis (1965: 340–433); reprinted in Davis (1994: 375–441).Post, Emil L. 1941[1965] “Absolutely Undecidable Problems and Relatively Undecidable Propositions — Account of an Anticipation”. Rejected by American Journal of Mathematics in 1941; posthumously published in Davis (1965: 340–433); reprinted in Davis (1994: 375–441)., the rejected autobiographical essay. But nothing remotely related to the mathematics of rewriting systems is touched on. And Robert Levine noted that Benny Brodda (1992Brodda, Benny 1992 “Comments [on Geoffrey Sampson’s paper ‘Probabilistic parsing’]”. Directions in Corpus Linguistics: Proceedings of Nobel Symposium 82, Stockholm, 4–8 August 1991 ed. by Jan Svartvik, number 65 in Trends in Linguistics Studies and Monographs, 448–453. Berlin: Mouton de Gruyter.Brodda, Benny 1992 “Comments [on Geoffrey Sampson’s paper ‘Probabilistic parsing’]”. Directions in Corpus Linguistics: Proceedings of Nobel Symposium 82, Stockholm, 4–8 August 1991 ed. by Jan Svartvik, number 65 in Trends in Linguistics Studies and Monographs, 448–453. Berlin: Mouton de Gruyter.: 449) has some remarks about Post’s production systems and refers to Rosner (1983Rosner, Michael 1983 “Production Systems”. Parsing Natural Language ed. by Margaret King, 35–58. London: Academic Press.Rosner, Michael 1983 “Production Systems”. Parsing Natural Language ed. by Margaret King, 35–58. London: Academic Press.: 35), a book chapter citing Reductions; but Rosner is a computer scientist, and his chapter contains no linguistics at all. There is nothing new about a computer scientist citing Reductions.

My conclusion is that it is just not credible that Chomsky attempted to suppress reference to two key mathematical papers that he knew about, concealing their significance so he could claim more credit for himself. His multiple mentions of Post’s name over the years (§ 5.2) would have to be explained as Freudian slips. The truth is that Chomsky was the only 20th-century linguist who ever even attempted to draw any attention to Post’s work. Others — even those with strong mathematical or historical interests — seem to have had no knowledge of the relevant papers.2020.Scholz and Pullum (2007Scholz, Barbara C. & Geoffrey K. Pullum 2007 “Tracking the Origins of Generative Grammar”. Journal of Linguistics 43.701–723. Scholz, Barbara C. & Geoffrey K. Pullum 2007 “Tracking the Origins of Generative Grammar”. Journal of Linguistics 431.701–723. : 721) comment on how historiographers of Chomsky’s work ‘often seem to be blinded by the light’ and use him as their guide to citation. Tomalin (2006)Tomalin, Marcus 2006 Linguistics and the Formal Sciences: The origins of generative grammar. Cambridge: Cambridge University Press. Tomalin, Marcus 2006 Linguistics and the Formal Sciences: The origins of generative grammar. Cambridge: Cambridge University Press. , for example, ‘followed Chomsky too closely and uncritically at many points’; in particular, ‘Because Chomsky never cites Post’s key technical papers, Tomalin likewise overlooks them’ — he cites only Post (1944)Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). Post, Emil L. 1944 “Recursively Enumerable Sets of Positive Integers and their Decision Problems”. Bulletin of the American Mathematical Society 50:5.284–316. Reproduced in Davis (1965: 305–337) and in Davis (1994b: 461–494). , and the same is true for Tomalin (2007)Tomalin, Marcus 2007 “Reconsidering Recursion in Syntactic Theory”. Lingua 117.1784–1800. Tomalin, Marcus 2007 “Reconsidering Recursion in Syntactic Theory”. Lingua 1171.1784–1800. . Yet Chomsky was not really in a position to tutor them, since (as he has plainly said) his own knowledge of Post’s work appears to have been limited to vague recollections of textbook accounts.

The point where Chomsky really gives insufficient credit relates to the two remarkable passages from Rosenbloom quoted earlier. The charitable view about this is that although they influenced his very early thinking (back circa 1950 when he was an MA student at Penn), Chomsky did not explicitly remember them. He later acknowledges Post’s place in the computability theory pantheon and credits Post with the term ‘generate’, but he nowhere mentions that Rosenbloom was the one who first saw that such systems might find an application in linguistics.

Chomsky’s work in formal linguistics, rich in original syntactic observations as it is, might well be seen as a 70-year project aimed at vindicating Rosenbloom’s suggestions, and that calls for some atonement. But it seems to me very likely that the solution to the puzzle of why he never cited Reductions or Unsolvability is simply that he never read them.