Yes, No, and Broader Contexts

Post’s generalization asserts: sequences generated (by a finite and mechanical process) can be generated by a normal system. In Sect. 7.4 we discussed some of Post’s reasons for accepting this assertion. They include an absoluteness argument that is similar to Godel’s; see footnotes 13 and 29. In his 1936 paper, Post emphasized the significance of proofs of the equivalence between different concepts. He claimed in (Post [45], p. 285) that there is an “overwhelming evidence” for the coextensiveness of the concept of recursive function “with the intuitive concept effectively calculable function”. As to the substance of the overwhelming evidence, Post referred to footnote 2 of (Kleene [31]) where Kleene summarized the considerations in favor of coextensiveness.[1] All of this fits perfectly well into the intellectual patterns of the early developments of computability theory and receives further strong support from the conceptual confluence of Post’s own work with Turing’s. In this sense then, Post did have Turing’s Thesis and accepted the standard arguments for it.[2]

However, in these considerations it is taken for granted that a notion of mechanical, algorithmic procedure is being analyzed. Godel emphasized in his [26] that finite procedure—in the context of undecidability and incompleteness results—must be understood as mechanical procedure. “This meaning, however,” he asserted, “is required by the concept of formal system, whose essence it is that reasoning is completely replaced by mechanical operations on formulas.” He added parenthetically:

Note that the question of whether there exist finite non-mechanical procedures, not equivalent with any algorithm, has nothing whatsoever to do with the adequacy of the definition of “formal system” and of “mechanical procedure”. (Godel [26], p. 72)

Post’s project had greater ambitions, arguing for the absolute unsolvability of combinatorial problems and concluding that the mathematical powers of Homo Sapiens are inescapably limited.

For Post to reach his ambitious goal, he needed a prima facie stronger generalization: sequences generated (by a finite process of the human mind) can be generated by a normal system. In addition, in order to obtain the connection to mathematics, the representation of mathematical states by symbol systems is required, as we discussed extensively in Sect. 7.6. That Gordian Knot is tied in a single step by appealing to a feature of the human mind that is epitomized by the remark “.. .what we are conscious of is not mathematics, but a formalization of it.” When drawing the conclusions concerning the limitations of the human mind, Post refers to “mental processes involved in combinatory mathematical processes”. (Anticipation, p. 55) On account of the structure of our mind, then, the combinatory mathematical processes involve for humans only finite mental processes that ultimately are captured by mechanical ones. Thus, a thesis or rather a sequence of theses has been formulated that is of a dramatically different character from Turing’s. And in that sense, Post did not have Turing’s Thesis, but rather a stronger “mental Thesis”. It supports, in particular, the claim made in Anticipation, “The fundamental new thing is that for the combinatory problems the given set of instruments is in effect the only humanly possible one.” This “mental Thesis” is subject to precisely the criticism that was incorrectly raised against Turing, when Godel in his [27] tried to pinpoint a “philosophical error in Turing’s work”; see (Sieg [53]).

Why did Post focus attention on finite processes of the human mind and insist on their psychological analysis? We saw in Sect. 7.7 that finite processes have to be considered because of the finitary character of symbolic logics; and that is necessitated in turn by the fact that they are a human product. The psychological analysis is to anchor the human way of doing logic and mathematics in features of the mind.


A related explanation could point to the influence of Post’s advisor Keyser. In his book Mathematical Philosophy, Keyser has a chapter devoted to the psychology of mathematics.[3] Mathematics is not only viewed as “an enterprise of the mind”, but it is also claimed, “mathematical phenomena represent mental phenomena” (Keyser [30], p.412; emphasis in the text). If we take, as Post certainly does, the structure and development of symbolic logics as mathematical phenomena, then the latter can be taken, following Keyser, as representing mental phenomena.

There might be a second point of influence, as Keyser ascribes great importance to the phenomenon of generalization, i.e., “the process by which the human mind from time to time enlarges the empire of its rational activity”. (Keyser [30], p.413) It is, after all, distinctive that Post calls his version of the identification claim generalization. Keyser discusses the generalization of the number concept as a significant example; indeed, he considers it to be one of “the probably best [specimens of generalization] to be found in the history of thought”. Through a succession of generalizations the domain of the number concept was extended from at first containing just the integers to “embracing”, as he puts it, “positives and negatives, rationals and irrationals, reals and imaginaries, cardinals and ordinals, including the transfinite numbers of Georg Cantor”. (Keyser [30], p.413) Not to allow suitable generalizations, according to Keyser, hampers progress in mathematics; he attributes the delay, by two thousand years, of “the advent of the concept of hyperspace and n-dimensional geometry” to a backward psychology of mathematics. (Keyser [30], p.407) Relating these observations back to Post, it was “the m-dimensional space analogy” that led him to introduce in Sect. 12 of his [38] a generalization of the classification of functions; generalization is also the broad theme of two of Post’s mathematical papers, his [40, 42].

Generalization and the attendant conceptual innovation were important to Post also in his [45], where he starts out with the observation, “Recent developments of symbolic logic have considerable importance for mathematics both with respect to its philosophy and practice.” The undecidability and incompleteness results support claims in the philosophy of mathematics, as they lead “to far-reaching conclusions on the nature of logical activity, and hence of mathematics”. (Anticipation, p. 48) The concept of recursive function or its proved equivalents is viewed as significant also for the practice of mathematics: Post wants to demonstrate “that this concept [of recursive function] admits development into a mathematical theory much as the group concept has been developed into a theory of groups”. He remarks, however, that only “a very limited portion of a sub-theory of the hoped-for general theory” is being developed in his own paper.

We can of course ask, what such a general theory in analogy to group theory might be. The development in Post’s [45] cannot be viewed as being analogous to group theory, as there is no abstract concept of computability under which particular notions of effectiveness fall: many different notions can be shown to be equivalent, but they don’t share the defining characteristics of such a general concept. What one might be looking for is perhaps best exemplified by the unifying, axiomatic treatment of different conceptions of “real numbers” that had been introduced in the second half of the 19th century, e.g., Dedekind cuts, Cauchy sequences, or Cantor fundamental sequences. In this case the relevant abstract concept is that of a complete ordered field; all the mentioned examples fall under it. In addition, if we take Dedekind cuts as our canonical reals, then every other complete ordered field is isomorphic to the system of cuts. (Thus, they are all isomorphic.)[4]

If one were to pursue a structural-axiomatic approach for computability, one would try to find an abstract concept under which the various models of computation fall. In analogy to proving that all complete ordered fields are isomorphic to the system of Dedekind cuts, one would try to prove in the computability case a representation theorem stating, the models falling under the abstract concept are all reducible to Turing machines. That approach has actually been pursued, see (Sieg [50, 51]); the abstract concept is that of a computable (discrete) dynamical system. The approach is thoroughly motivated by the confluent work of Post and Turing and their attempts to consider “wider formulations”, i.e., configurations and local operations on them that are more general than those permitted in canonical systems or substitution puzzles. Their mathematical work and their methodological reflections have inspired the definition of a computable dynamical system and the proof that this abstract concept is equivalent to that of a Turing machine.

The general point is then this: the characteristic conditions of computable dynamical systems articulate minimal abstract conditions that a combination of finite configurations and mechanical operations have to satisfy to still count as a “wider formulation” or as a “puzzle”. Thus, we don’t have to face a mysterious thesis for the concept of computability; we rather have to face the ordinary and very hard issues for judging the adequacy of a mathematical concept to capture aspects of our intellectual or physical experience.

Acknowledgements We thank Martin Davis, Liesbeth De Mol, and Ulrik Buchholtz for encouraging, but also critical remarks. Liesbeth’s detailed comments prompted real changes in our presentation. We are also very grateful to Alberto Policriti and Eugenio Omodeo, who as editors of this volume were extremely patient with our difficulties completing this essay.

  • [1] For the reader’s convenience, we quote the essential points of Kleene’s footnote, which is attachedto the statement, “A function of natural numbers, with natural numbers as values, is taken to beeffective if it is Herbrand-Godel recursive.” Here is the (partial) quote: . .This notion of effective ness appears, on the following evidence, to be general. A variety of particular effective functionsand classes of effective functions (selected with the intention of exhausting known types) havebeen found to be recursive. Two other notions, with the same heuristic property, have been provedto be equivalent to the present one, viz., Church-Kleene Л-definability and Turing computability.Turing’s formulation comprises the functions computable by machines. . Functions determinedby algorithms and by the derivation in symbolic logics of equations giving their values (provided theindividual steps have an effectiveness property which may be expressed in terms of recursiveness)are recursive.”.
  • [2] We contended in Sect. 7.7, turning “Post’s analysis on its head”, that one can extract from hisanalysis, when stripped of philosophical preconceptions and reversed, an argument that is strikinglysimilar to Turing's.
  • [3] Post finished his graduate education in 1920; Keyser’s book was published only in 1922. Yetit is most likely that Post was familiar with Keyser’s views expressed in the book. In the Preface(page vii) Keyser mentions that the book is the result of more than forty years of reflection on thenature of mathematics.
  • [4] The underlying distinction between structural and formal axiomatics is discussed in Sieg [54].
< Prev   CONTENTS   Source   Next >