A Natural Law: Inescapable Limitations
In the introductory remarks to the Appendix of Anticipation, Post reemphasizes that the undecidability and incompleteness results are “evidences of limitations in man’s mathematical powers”. (Anticipation, p. 56) In a similar vein Post had noted in (, p. 105, fn. 8), as a consequence of these results, “that a fundamental discovery in the limitations of the mathematizing power of Homo Sapiens has been made”. The limitations are explained more comprehensively in the first footnote of Anticipation:
[...] The writer cannot overemphasize the fundamental importance to mathematics of the existence of absolutely unsolvable combinatory problems. True, with a specific criterion of solvability under consideration, say recursiveness, the unsolvability in question, as in the case of the famous problems of antiquity, becomes merely unsolvability by a given set of instruments. And, indeed, the corresponding proofs for combinatory problems are almost trivial in comparison with the classic unsolvability proofs. The fundamental new thing is that for the combinatory problems the given set of instruments is in effect the only humanly possible set. (Anticipation, p. 1, fn. 1)
The last sentence, with its claim that “the given set of instruments is in effect the only humanly possible set” for solving combinatory problems, receives more concrete content in a footnote that points to the central methodological problem that has to be resolved in order to justify the claim:
Since the earlier formal work made it seem obvious that the actual details of the outline [for the proofs of the above results] could be supplied, the further efforts of the writer were directed towards establishing the universal validity of the basic identification of generated set with normal set. (Post , p. 215, fn. 18, our emphasis)
Post clearly does not see this identification as a definition; after all, he intends to establish its universal validity.
One direction of the identification, i.e., normal sets are generated ones, is taken to be correct; thus, the inclusion of generated sets among the normal ones is at issue and is seen by Post as a “partially verified conclusion”. (Anticipation, p. 3) This was articulated also in his  from 1936, where Post conjectured that wider and wider formulations (of generating systems) would all be logically reducible to his “formulation 1”. He considered this conjecture as a “working hypothesis” which would be changed by the successful pursuit of the reductive program “not so much to a definition or axiom but to a natural law”. (Anticipation, p. 105) Indeed, Post observed, “the work done by Church and others [establishing equivalences of various formulations] carries this identification considerably beyond the working hypothesis stage”. The natural-law-perspective is expressed again in a footnote to his (, p.286). Post mentions there that Kleene had used “Thesis” as a label for the identification. However, in contrast to Kleene, Post feels “that, ultimately, ‘Law’ will best describe the situation” and points out, via his  paper, that this law is in need of “continual verification”. (, p. 105, fn. 8)
How can such a natural law be verified, continually? The short answer to the question is, by the kind of “physical induction” Post appealed to in his letter to Godel, written on 30 October 1938. We quoted from that letter at the end of Sect. 7.5, namely, that the absolute unsolvability of the decision problem for all normal systems “has but a basis in the nature of physical induction...”. Post then claims with respect to Godel’s own logical system, a version of Principia Mathematica, “that [physical] induction could have gone far enough to include your particular system theoremat- ically”. (Godel , p. 171) That means he could have proved, as he had done for (subsystems of) Principia Mathematica, that Godel’s system is also reducible to a normal system. So it seems that the reduction of particular systems, or of wider formulations, to one of his canonical systems has the point of inductively strengthening the evidence for the problematic half of the identification.
Post asserted forcefully in 1936 that the identification should not be masked under a definition; this is directed against Church who had proposed in his  to definitionally identify effective calculability with recursiveness. Church challenged this assertion in his review of(Post) by saying, “effectiveness in the ordinary sense has not been given an exact definition, and hence the working hypothesis in question has not an exact meaning”. Church’s remark is correct, but does not undermine Post’s program of inductively strengthening the connection between the informal concept of generated sets and the mathematically defined normal ones. Whatever is done in support of Post’s reductive program is useful, and indeed necessary, to justify the use of “effectively calculable” in Church’s definition. We seem to be at a standstill of an almost purely terminological kind.
At this point a substantive question should be raised. Assume that the generalization has indeed been confirmed as a natural law; does it support Post’s claim concerning the limitation of human mathematical powers? An attempt to answer this question reveals that much more than a terminological choice is at stake. Indeed, a crucial turn in argumentation is required that brings in not only the human mind and its way of understanding mathematics, but also the mediating role of symbolic logics. For syntactically complete theories the connection between (informal) mathematics and its representation in symbolic logics is unproblematic and direct. That was taken for granted by Post in his  and was discussed in Part 1. If all symbolic logics are incomplete, then the connection has to be anchored in some other way.
Having restated that the development in §§9-10 of Anticipation concerning undecidability and incompleteness “owes its significance entirely to the universal character of our characterization of an arbitrary generated set of sequences as given in §7”, Post points to this new direction at the beginning of the Appendix to Anticipation. He disowns the idea that the considerations of §7, as described in Sect. 7.4, were intended as a proof-like argument. Instead, he claims famously:
Establishing this universality is not a matter of mathematical proof, but of psychological analysis of the mental processes involved in combinatory mathematical processes.
(Anticipation, p. 55)
What role such a psychological analysis might play is further clarified by a distinction Post makes in footnote 6 of Anticipation. There he separates “a formulation which includes an equivalent for every possible ‘finite process’ ”, from “a description which will cover every possible method for setting up finite processes”.
The psychological analysis aims for a suitable description covering “every possible method for setting up finite processes”; that theme had already been alluded to at the end of §8:
But for full generality a complete analysis would have to be made of all the possible ways in which the human mind could set up finite processes for generating sequences. The beginning of such an attempt will be found in the Appendix. (Anticipation, p. 48)
We will now point to the crucial stages of Post’s attempt to arrive at full generality. The beginning of the needed complete analysis is described as follows:
We begin here a derivation of the logic of finite operations and ultimately of all of the logic of mathematics from first principles. These principles are supposed to be a digest of our experience of the logico-mathematical activity... (Anticipation, p. 56)
The logico-mathematical activity is, of course, an activity of the human mind “as situated in the universe”, and its objects “may be anything in the universe”. Its method “seems to be essentially that of symbolization”. The use of language is for Post a central symbolizing activity:
It may be noted that language, the essential means of human communication is just symbolization. (Anticipation, p. 57)
Leaving aside a detailed discussion of one feature of this activity Post considers as important (and we don’t fully understand), namely, its self-consciousness, we point to one central effect through this fundamental remark of Post’s:
_we shall here not consider the original objects which are symbolized, but only the relations and operations upon these resulting symbols... (Anticipation, p. 57)
It is essential “that these symbols enter into certain spatial relations”. The “result of logical thought” is conceived of as a “spatial configuration of symbols”. For the study at hand, “We are to regard our symbols as without properties except that of permanence, distinguishability and that of being part of certain symbol-complexes.” (Anticipation, p. 57) Consequently, the core of the project is now “an analysis of these spatial relations.”
After a long and complex discussion of “the creative germ of the thinking process” and the nature of proof, Post returns on page 62 of Anticipation to the analysis of symbolisms in connection with finite processes. He presents a summary of the “method” for obtaining a description and indicates which of its elements, in addition to mere symbols, constitute the sought-after description:
We return here to a more complete discussion and analysis of the very first part of the present research i.e., in connection with finite methods. We shall here generalize to finite methods for obtaining any results not just test for truth and falsity.
We shall here first give what is at least a first approximation to a definitive solution of finding a natural normal form for symbolic representation.
There are three stages in the analysis we give. In the first stage we have the things symbolized. ...
This then gives us our second stage in our analysis, namely a system of symbolizations for corresponding mathematical states. (Anticipation, p. 62)
The subsequent reflections are concerned with the symbolizations that are now assumed to be finite and discrete (and we will come back to them in the next Part.) As to the correspondence between symbolizations and mathematical states, Post asserts:
Now the system of symbolizations in question is essentially to be a human product and each symbolization [is to be] a human way of describing the original mathematical state.
(Anticipation, p. 63)
A discussion of the “third and last stage in this analysis” follows. The symbolizations “represent the original mathematical states” and, given the finiteness and discreteness assumptions, they can be “completely described”. Post finally concludes, “Hence these descriptions can be considered to represent or symbolize those mathematical states.” (Anticipation, p. 63)
The above remarks are all taken from the main text of the Appendix, i.e., from Post’s notes and diary from the 1920s. In footnote 120, the very last of the footnotes that comment on the early work and were written 15 to 20 years later, Post quotes a remark from the 1920s that makes explicit, how he thought of his work at that time: “The main outline of the work is completed and we really have a case of Filling In.” Post then continues the footnote with this devastating judgment:
Actually, but the surface of the problem was thus, perhaps, barely scratched, the problem, that is, of describing “all the finite processes of the human mind,” at least in so far as they might concern the generalization of §7. (Anticipation, p. 67)
So it seems that the hoped-for description, “which will cover every possible method for setting up finite processes”, had not been achieved in Post’s own judgment. However, given the basic assumptions, he may very well be seen as having arrived at a formulation “which includes an equivalent for every possible ‘finite process”’; that is indeed Post’s considered judgment. (See footnote 26 above.) We will examine this issue in Sect. 7.7.
-  Turing, in his illuminating and informal paper from 1954, entitled Solvable and unsolvable problems, formulates the thesis not for mechanical procedures or generated sets, but rather for puzzlesas follows: “The normal form for puzzles is the substitution type of puzzle [i.e., a particular kindof Post canonical system].” He remarks then, “The statement is moreover one which one does notattempt to prove. . for its status is something between a theorem and a definition. In so far aswe know a priori what is a puzzle and what is not, the statement is a theorem. In so far as we donot know what puzzles are, the statement is a definition which tells us something about what theyare.” (Turing , p. 15) As puzzles can be given “finite coordinates”, they are more general syntactic configurations. It should be mentioned that Post also considered broader classes of syntacticconfigurations; see (Urquhart , p. 643).
-  Kleene, straddling Post’s and Church’s positions, wisely remarked in his , the classical Introduction to metamathematics, “While we cannot prove Church’s thesis, since its role is to delimitprecisely an hitherto vaguely conceived totality, we require evidence that it cannot conflict withthe intuitive notion which it is supposed to complete; i.e. we require evidence that every particularfunction which our intuitive notion would authenticate as effectively calculable is general recursive.The thesis may be considered a hypothesis about the intuitive notion of effective calculability, or amathematical definition of effective calculability; in the latter case, the evidence is required to givethe theory based on the definition its intended significance.” (Kleene , pp. 318—9).
-  In footnote 12 of Anticipation, Post asserts that “the bubble of symbolic logic as universal logicalmachine finally [has] burst” on account of the undecidability and incompleteness results; he adds,“Actually, the old dream of symbolic logic is finding partial realization in Tarski’s recent work ondecision problems.”
-  In the very footnote in which Post articulates this difference, he also asserts that the first goal hasbeen achieved by the work in §7. The contributions to the proposed complete analysis, needed toachieve the second goal, are fragmentary. They are sometimes quite obscure and difficult to grasp, inparticular, those related to the “analysis of proof” with the goal of finding an absolutely undecidableproposition. See Anticipation footnotes 4 and 6 as well as the remarks on the “process of proof’starting on page 59. Post writes, the limitations in man’s mathematical powers “suggest that in therealms of proof .a problem may be posed whose difficulties we can never overcome; that is that wemay be able to find a definite proposition which can never be proved or disproved.” (Anticipation,p. 56) Then he refers back to footnote 1 in which he describes, more expansively, a “fundamentalproblem”, namely, the question of “the existence of absolutely undecidable propositions which insome a-priori fashion can be said to have a determined truth-value, and yet cannot be proved ordisproved by any valid logic.” (Anticipation, p. 1) That is, of course, in striking opposition to therationalist optimism of Hilbert and Godel that is beautifully expressed in (Godel , p. 164).
-  From Latin ‘digesta’ (n., pl.) meaning ‘Matters methodically arranged’.
-  Recall from Sect. 7.2 the non-semantic understanding of truth and falsity.