Reasons for a Thesis

In §§7-10 of Anticipation, Post asserts and sketches proofs of results he had obtained in the early 1920s. These results are analogues of the undecidability and incompleteness theorems Turing and Godel presented in their papers of 1936 [56] and 1931 [22], respectively. For the undecidability of predicate logic in particular, an adequate concept of computability or mechanical procedure is needed relative to which unsolvability is shown. The adequacy of such a concept is usually expressed as a Thesis, most often as Turing’s Thesis, Church’s Thesis, or the Church-Turing Thesis. Post formulated an assertion that is equivalent to those theses; he called it simply generalization, but it was dubbed Post’s Thesis by Davis in his [10]. We describe now the considerations that led up to it and made it ultimately plausible to Post. Let us start out by quoting Post’s own formulation at the end of §7 of Anticipation:

Every generated set of sequences on a given set of letters a1, a%, ..., a_M is a subset of the set of assertions of a system in normal form with primitive letters a1, a2, ..., a_M, aj, a'₂,

..., a'^, i.e., the subset consisting of those assertions of the normal system involving only the letters a1, a2, ..., a_M. {Anticipation, p. 46)

Post had shown in §2 of Anticipation, as we discussed earlier, that parts *10 and *11 of Principia Mathematica are reducible to a single system in canonical form B. He made an even stronger claim now:

From this experience, and the knowledge of the kind of forms and kind of operations appearing in the whole Principia Mathematica [___] it becomes reasonably certain that all of Prin-

cipia Mathematica can in similar fashion be reduced to a system in canonical form B.

(Anticipation, p. 44)

As canonical form B is reducible to canonical form C and the latter to normal form, it is reasonable to believe that the whole system of Principia Mathematica is reducible to normal form.

If then we think of canonical form C as a method of generating a set of (finite) sequences [_], we see that the generated sets of sequences yielded by all systems in canonical form C are the same as those yielded by the formally simpler normal systems.

(Anticipation, p. 45, our emphasis)

However, to make the Thesis plausible, one has to argue that normal systems indeed yield all generated sets of sequences (over a finite alphabet). Post advances two arguments for this claim: the first establishes the reducibility of very general kinds of wider formulations to normal systems; the second shows that the familiar method of diagonalization does not lead out of the sets generated by normal systems.

The first argument starts out, in the last paragraph on page 45 of Anticipation, with the observation that the premises and conclusion of any production rule of a system in canonical form C can “completely be described in logical terms and the primitive relation of precedence in a sequence”. The meaning of “logical terms” is not specified, but the later part of §7 provides the basis for a suitable interpretation: the properties of production rules of systems in canonical form C and their operations can be expressed in the language of Principia Mathematica. That is, one can express that a given string is obtainable from a given premise by substituting certain primitive letters into the operational variables, that a sequence of strings contains instances of all the premises of a given production rule and that its consequence can be produced; thus, the generation of sequences can be represented in Principia Mathematica together with some postulates for sequences.

Such an embedding of systems in canonical form C in an expanded system of Principia Mathematica “suggests the possibility of describing more complicated operations for the purpose of generating sets of sequences.” (Anticipation, p.45) For it might be that the whole apparatus of Principia Mathematica is capable of expressing more complex operations than those that can be given by production rules of canonical form C. Thus, these possibly more complex operations have to be accounted for by arguing that the sets of sequences generated by them can be generated by systems in form C and, in turn, by normal systems. Post asks us to suppose that each operation is of the form, “a certain number of premises, described in logical terms, gives rise to a certain conclusion, likewise described”. (Anticipation, p.45) They may consequently be written in the form: P₁, P₂, ..., P_k produces P, where P_b P2, ..., Pk, P have certain properties fi(Pi), /2(P2), ..., fk(Pk), f (P). In addition, suppose that a set of postulates on the letters a₁, a₂, ..., a,_л is fixed and “Principia Mathematica is used as the logic of the resulting mathematical system”, which Post calls sequence-Principia Mathematica system. (Anticipation, p.46) Granting the generality of Principia Mathematica, sequences P₁, P₂, ...,

P_k, P will have the properties f₁(P₁), f₂(P₂), , f_k(P_k), f (P) if the latter are

assertions in the sequence-Principia Mathematica system. (Anticipation, p. 46) Then, the operations can be written in the form: f₁(P₁), f₂(P₂),..., f_k(P_k), f (P), P₁, P₂, ..., P_k produce P .Asa result, the system for generating sequences on a₁, a₂, ..., a_p is the system of Principia Mathematica supplemented “by certain postulates and operations of the same general type”. (Anticipation, p.46) Notice the condition that postulates and operations are to be of the same general type as those of Principia Mathematica. This is essential in the following argument.

Principia Mathematica can be reduced to a system in normal form and, with the supposition emphasized in the previous paragraph, reducibility can be expected of the expanded system as well. (Anticipation, p.46) That is, even after Principia Mathematica has been expanded to a system for generating sets of sequences using complex operations, it is plausible that a system in normal form can be set up, such that the set of its assertions involving only the letters a₁, a₂, ..., a_p is the same as the set of sequences generated by the expanded Principia Mathematica system. This conclusion led Post to the generalization we quoted earlier and called, following Davis, Post’s Thesis. The reasons are for Post “the generality of the system of Principia Mathematica, and its seeming inability to lead to any other generated sets of sequences on a given set of letters than those given by our normal systems”. (Anticipation, p. 46) The recognition of the significance of this web of reductions led, as Post put it at the end of §6, “to a reversal of our entire program” (Anticipation, p.44) that had been aiming for a positive solution of the general finiteness problem.

Let us come, finally, to the second argument we mentioned at the beginning of this part. Using a diagonal argument an apparent counterexample to Post’s Thesis can be constructed from specially generated sets of sequences. According to the Thesis, the generated sets of sequences that involve only the letter a are subsets of assertions of normal systems with letters a, a₁, a₂, ..., a_p, where p = 0, 1, 2,... Given the definition of normal systems, it is clear that there are only enumerably many of them. For a fixed enumeration, we can define a set D_a of a-sequences: D_a contains the sequence a^m of ma ’s if and only if a^m is not an assertion of the m-th normal system. Da differs from the set of assertions of each normal system, as it disagrees with the m-th such system on a^m. Post remarks that this set is not a counterexample to the thesis; after all:

[We] have merely defined a set of a-sequences, whereas to yield a true counter-example we must show how to generate that set, i.e., set up a system of “combinatory iteration” whose operations would at some time yield each and every a-sequence in that set, but would never yield an a-sequence not in the set. (Anticipation, p. 47)

However, were the finiteness problem solvable for normal systems, the above set could be generated, as any solution would decide, in particular, whether or not the a-sequence of length m is an assertion of the m-th normal system.

That is, a solution of the finiteness problem for all normal systems would yield a counterexample disproving the correctness of our proposed generalization. (Anticipation, p. 47)

Thus, we are led to the following biconditional: Post’s Thesis holds if and only if the flniteness problem for normal systems is unsolvable.

Post points out, “nothing in the above argument weakens the reasoning that led us to our generalization”. (Anticipation, p. 47)^[1] It should be remarked that Post’s unsuccessful attempts to solve the flniteness problem for tag systems made the unsolvability of normal systems plausible to him and committed him to his generalization even more strongly^[2]:

We therefore hold on to that generalization and conclude that the finiteness problem for the class of all normal systems is unsolvable, that is, that there is no finite method which would uniformly enable us to tell of an arbitrary normal system and arbitrary sequence on the letters thereofwhether that sequence is or is not generated by the operations of the system from the primitive sequence of the system. (Anticipation, pp. 47-8)

Thus, we have an informal sketch of an argument for the undecidability of the sequence-Principia Mathematica system, on account of the unsolvability of the flniteness problem for normal systems and their connection to sequence-Principia Mathematica via canonical systems of form B and C. The unsolvability of the flniteness problem rests on the argument leading to the generalization (i.e., Post’s Thesis), which in turn depends crucially on the supposition that the operations and postulates of the full sequence-Principia Mathematica system are all of the same general type. Thus, the methodological issue revolves around the question of why only extensions of this restricted form should be admitted.^[3] In the next part we take the Thesis for granted and, with it in the background, look at the proof sketches Post provides for his analogues of Turing’s undecidability result and Godel’s first incompleteness theorem. In Sect. 7.6 we will come back to the “central methodological issue”.

• [1] Kleene was convinced by the same argument; see (Kleene [33], p. 59). In (Post [45], p. 285)“overwhelming evidence” is adduced for Church’s Thesis by reference to footnote 2 in (Kleene[31]). There one finds a concise and masterful summary of the evidence, as Kleene saw it, for the“identification” of effective calculability and recursiveness; Kleene’s remarks are quoted in footnote34, below.
• [2] The tag systems are special normal systems: the g’s are all of the same length; each g' dependsonly on the first letter of its corresponding g.—The important role of the problem of “tags” wasemphasized in §3 of Anticipation; see also the very careful analysis in (De Mol’s [16, 17]). Indeed,De Mol argues that the tag systems were crucial for Post for two main reasons: (1) they promptedhis belief that there might be absolutely unsolvable problems, and (2) they inspired the formulationof normal systems.
• [3] The character of this argument and its similarity to “absoluteness” considerations of Godel,Church, Hilbert & Bernays, and Turing will be discussed briefly in footnote 29 of Sect. 7.7 below.—Martin Davis pointed out that the above considerations of course do not establish the undecidabilityof predicate logic. Post is very cautious on what he claims to have established with respect to thatproblem; see footnotes 79 and 90 of Anticipation and also footnote 10 above.