# Symbolic Logics: Finitary Constraints

What Post did not argue for explicitly at all, except “dogmatically”, is the correspondence between mathematical states and finite and discrete symbol complexes, with the latter in some sense representing the former. The nature of that representation is crucial for the claim that the undecidability and incompleteness results constitute a discovery of limitations of the mathematizing power of Homo Sapiens. After all, those results concern straightforwardly only symbolic logics in which mathematics can be developed. Post writes in footnote 12 of Anticipation, “Symbolic Logic may be said to be Mathematics become self-conscious.” And the former is according to Post by necessity finitary.

The finitary feature of symbolic logics is crucial not only for Post but also for Church and logicians in general, when they insist on an effective concept of deduction. In Anticipation Post asserts:

Where we say “symbolic logic” the tendency now is to say “finitary symbolic logic”. However, it seems to the writer that logic should be considered essentially a human enterprise, and that when this is departed from, it is then incumbent on such a writer to add a qualifying “non-finitary”. (Anticipation, fn. 10)

In his ([45], p.288) Post leaves out the qualifying “finitary” when writing, “The assertions [theorems] of an arbitrary symbolic logic constitute a generated set A of what may be called symbol-complexes or formulas.” He justifies the omission in a footnote referring to (Church [7]), where Church defends an effectiveness criterion

that “necessarily applies” to inference steps or rules of procedure of any “formal system of logic”:

There is some current tendency to apply the name “logic” to schemes which are similar to accepted systems of logic, but involve one or more rules of procedure which lack this characteristic of effectiveness. Such schemes may perhaps be of interest as abstract definitions of classes of formulas, but they cannot in my opinion be called “logics” except by a drastic (and possibly misleading) change of the usual meaning of that word. For they do not provide an applicable criterion as to what constitutes a valid proof. (Anticipation, p. 225)

This remark not only reflects the normative requirement that logics should have an applicable, i.e., decidable proof predicate, but also Church’s considerations in his classical 1936 paper [5]. There Church argued that all functions “computable in a logic” are recursive by his well known step-by-step argument; see (Gandy [21]) or (Sieg [49]). For Post this would be of interest, but certainly not conclusive, as the identification of decidable and recursive is taken for granted.

When discussing §7 of Anticipation in Sect.7.4 above, we saw an attempt to give a convincing argument for a reducibility claim that is analogous to Church’s: given any expansion of Principia Mathematica by “postulates and operations of the same general type” one can set up an equivalent normal system.[1] In his [44], Post formulates a broader claim. He writes that the methods developed for the reduction of systems of form C to normal systems led him to conclude,

that not only Principia Mathematica, but any symbolic logic whose operations could effectively be reproduced in Principia Mathematica, and hence probably any (finitary) symbolic logic could be reduced to a system in canonical form, and consequently to a system in normal form. (Post [44], p. 215, fn. 18)

In his letter to Godel we quoted earlier, Post states straightforwardly that any symbolic logic is reducible to normal form. How this can be achieved and given a philosophical grounding was indicated already in Part 5, when we examined his analysis of symbolizations. We quoted there an extended passage from Anticipation that ended with the sentence “This gives us our second stage in our analysis, namely a system of symbolizations for corresponding mathematical states.” As we saw, symbolizations are taken to be spatial configurations and are assumed to be finite and discrete. They are constituted from parts that are unanalyzable in a given discussion, but have certain properties and stand in particular relations. They are, as we discussed, a “human product” and a “human way of describing the original mathematical state[s]”. Thus, Post asserts, the need for the following assumption is readily seen, namely,

that the number of these elementary properties and relations used is finite and that there is a

certain specific finite number of elements in each relation. (Anticipation, p. 63)

This is the basis for the third and last stage of Post’s analysis, namely, the complete “finite and normal” description of the symbol complexes.

Corresponding to the three stages in the analysis of symbolizations, Post considers three stages in the analysis of methods. The first and rather inchoate stage consists of “any and all methods” [emphasis in the text]. “To allow for the most wonderful creations”, Post elaborates, “my image of such methods involved dark clouds pierced by flashes of lightning accompanied by rolling thunder.” Some of these methods are symbolized at the second stage, and their application results in a finite sequence of symbol-complexes “due to discreteness and finiteness”. The third stage then consists in “reducing the method of passing from symbol complex” to an operation of “normal type”. Such normal operations apply to the complete description of symbol complexes obtained at the third stage of the analysis of symbolizations. The underlying process is iteration and is viewed as mechanical, “merely machine like” (cf. also footnote 87).

The philosophical grounding of these third stages of Post’s analyses is in both cases given through only vaguely conceived conscious experience of mathematical states, respectively in similarly unstructured methods; it is obviously problematic and, in the end, quite dogmatic. The dogmatic aspect relates in particular to consciousness, concerning which Post simply remarks in (Anticipation, p. 65): “...what we are conscious of is not mathematics, but a symbolization of it.” [emphasis in the text]. Recall that symbolizations are assumed to be finite and discrete—on account of the fact that their system is essentially a “human product” and “each symbolization a human way of describing the original mathematical state”. Is it in this sense that Post made the remark we chose as the motto for our paper “.I study Mathematics as a product of the human mind and not as absolute.”?—In any event, the presumed grounding of finiteness and discreteness assumptions in features of the human mind or consciousness is rather ineffectual. And yet, only such a grounding, together with connections to mathematical states, would give support for the sweeping claims of absolute unsolvability and, as a consequence, of the inescapable limitation of human mathematical thinking.

Let us try now to turn Post’s analysis on its head to see the similarity and radical difference to Turing’s argument for his thesis. When reflecting on the reduction of the logic of finite operations to finite and discrete symbol complexes and operations of a normal type, Post articulates most clearly, that “only elementary recognition seems to be needed for the logical aspect of the operational description of mathematics”. The nature of such elementary recognition is indicated, for example, by Post’s remarks concerning judgments about symbol complexes: “a single undivided act of judgment” is required for recognizing the crucial properties of and relationships between parts of a symbol complex (Anticipation, p. 63). So, if we disregard the connection to mathematical states and focus purely on symbolizations (without meaning), then the requirement to appeal only to elementary recognition would seem to justify the flniteness and discreteness assumptions for symbol complexes—quite in Turing’s way; the restricted mechanical, machine-like character of operations is taken for granted anyway. In this way Post’s analysis is cut off not only from stage one (as Post himself does), but also from stage two. When Post’s views are articulated in this way, his reversed argument that starts with (the demand for) elementary recognition and ends with flniteness conditions is strikingly similar to that Turing gives in 1936 in his [56] for the claim that the mechanical operations of a human computer can be carried out by one of his machines.[2]

Relating Turing’s analytic work to his own, Post notes the parallelism, but retains the connection of the last two stages and remarks:

Fundamental is the distinction between the static outer symbol-space with its assumed capacity of unbounded complexity, and the dynamic mental world with, however, its obvious limitations. This has been fully captured by Turing in his finite number of mental states hypothesis. (Anticipation, fn. 118)

States of mind of human computers do play a critical role for Turing’s analysis in Part I of Sect. 9 of his paper. In analogy to the flniteness constraint on immediately recognizable sequences, Turing asserts also that human computers have only a finite number of states of mind. However, Turing replaces states of mind by “a more physical and definite counterpart” (in Part III of the very same section):

It is always possible for the computer to break off from his work, to go away and forget all about it, and later come back and go on with it. If he does this he must leave a note of instructions (written in some standard form) explaining how the work is to be continued. This note is the counterpart to “state of mind”. (Turing [56], p. 253)

Thus, it is not clear in what sense Turing’s final analysis uses a “finite number of mental states hypothesis”; it is also not clear at all in what sense it would capture fully “the dynamic mental world... with its obvious limitations”.[3] Turing, as is clear from the last quote, describes mechanical procedures that are completely external to the computing agent; these externalized computations are the objects of his analysis, not mental states or the human mind. Some cognitive capacities are of course taken for granted, but for his restrictive analysis Turing appeals to only one obviously psychological fact, namely, the limitation of the human sensory apparatus; it and only it provides the basis for the fundamental finiteness and locality conditions.

These considerations are directly and beautifully mirrored in Post’s description of Turing machines and their computations in his [46] from 1947.[4] His mathematically precise description via a form of canonical system is used to prove the undecidability of the word problem for semi-groups by reducing it to the halting problem for Turing machines. Turing was impressed by the result and the method of proof; in his [58] he extended the undecidability result to semi-groups with cancelation. The discussion of the methodological and mathematical issues surrounding computability in his [59] does not mention machines; the issues are rather articulated exclusively in terms of puzzles and substitution puzzles, i.e., particular canonical systems.[5] That naturally underlines the conceptual confluence in their work: it is also, it seems to us, an expression of deep appreciation. The latter is, of course, also expressed in the abstract of (Turing [58]), when he describes the word problem as being reduced to an unsolvable problem that is “connected with the logical computing machines introduced by Post and the author”, referring to (Post [41]) from 1936 and his own classical paper from the same year.

• [1] Post’s argument for this assertion resembles Godel’s for the absoluteness of the notion of computable functions in his [24, 26]. A similar argument for identifying the notion of calculable functions with recursiveness is found in Church’s letter to Pepis from June 8, 1937, which is reprintedin the Appendix of (Sieg [49]). Each argument shows that, as long as broad informal conditions aresatisfied, the extensions of particular kinds don’t allow for more computations than the restrictedframeworks. Considerations of the same kind are found in Supplement II of Hilbert & Bernays’sGrundlagen der Mathematik II as well as in (Turing [56], Sect.9, II).—This notion of “absoluteness”, obviously quite different from Post’s, is discussed in (Sieg [51], 572-7). We should pointout that Post’s argument suffers from the same kind of subtle circularity as Godel’s and Church’s,because it is required that the extensions have to have postulates and rules of the same general formas those of Principia Mathematica.
• [2] Turing’s argument was analyzed in (Sieg [48]); it is put into a broader systematic framework in(Sieg [51]).
• [3] Turingis discussed in notes 6,9,112,118, and 120 of Anticipation. Post most strongly emphasizesthe role of the “finite number of mental states hypothesis”. However, why would its correctnessmake Post’s position (as he remarks in note 9) “largely academic”? And, why would it make (ashe says in note 6) “the detailed development envisioned in the Appendix unnecessary”? - Post isgrappling with a different problem; in addition, it is not just the number of mental states that isimportant for Post’s considerations, but also their internal elementary, discrete structure. (Widerformulations, as stressed in [41], are to achieve greater psychological fidelity.).
• [4] Note in particular that the internal configurations of machines or m-configurations, which correspond to the states of mind of the human computer, are directly incorporated into the symbolicconfigurations on which the (Post) production rules operate.
• [5] See (Sieg [52]) for the discussion of this variant of Turing’s Thesis introducing a normal formsfor puzzles; see also footnote 23.