Introduction

In 1936, Post and Turing presented two models of computation that were essentially identical. Turing, in his long paper, argued for the adequacy of his model and proved that the Entscheidungsproblem for predicate logic is unsolvable by procedures that can be carried out by his machines; Post, in his very short paper, described his model and only conjectured that it is equivalent to Godel’s (general) recursive functions.1 The Entscheidungsproblem for subsystems of Principia Mathematica, including one corresponding to predicate logic, had motivated Post’s work already in the early 1920s. Post’s and Turing’s focus on this particular finiteness problem concerning syntactic configurations was perhaps the reason for developing a common perspective. Undoubtedly, theirs is a uniquely direct approach to combinatory procedures and stands in stark contrast to Godel’s indirect way via (effectively) calculable number theoretic functions. The latter way was, however, straightforwardly and strongly rooted in mathematical practice.

Indeed, the experience with number theoretic calculation procedures had crystallized, in the late 19th and early 20th century, into the concept of primitive recursive functions. That concept is found in Dedekind’s [15]. Skolem as well as Hilbert and Bernays used it extensively throughout the 1920s. Godel [22] in 1931 put this class of functions to work for the arithmetization of syntax in his proof of the incompleteness theorems. In the 1934 Princeton lectures, he defined the larger class of (general) recursive functions. The precise mathematical notions introduced by Godel, Church, and Turing were eventually shown to be equivalent. However, Church had already in late 1935 suggested identifying the informal concept of calculable functions with that of recursive functions. The history of and the arguments surrounding Church’s Thesis will not be reviewed here; there are, after all, comprehensive accounts in the literature, e.g., (Kleene [32], Sects. 62 and 70), (Gandy [21]), (Sieg [48, 51]).

Turing’s model of machine computation has been recognized as special, in part because it vividly captures the “mechanical” aspect of algorithmic procedures. More important is Turing’s argument from 1936, given in Sect. 9 of his [56], that any mechanical procedure carried out by a human computer can be executed by one of his machines, a claim now labeled Turing’s Thesis. His analysis has great intuitive appeal and articulates restrictive boundedness and locality conditions, but it does not constitute a proof of the general claim. Turing’s argument does prove a suitably restricted claim, if one focuses attention on finite strings of letters from a finite alphabet and accepts the above conditions for strings and operations on them. We will come back to this argument later on, as it is precisely here that Turing’s and Post’s approaches diverge.

1 Church [2] had obtained, also in 1936, the same unsolvability result as Turing. He used Godel’s recursive functions, which he knew to be equivalent to the Л-definable ones, as the precise notion of computability.

Post does not argue in his 1936 paper that the worker in his model, when operating in the given symbol space, can carry out all combinatory processes, but suggests contemplating “wider and wider formulations” and reducing them to his so-called formulation 1. Nevertheless, he makes the enigmatic claim that the incompleteness and undecidability results brought to light “that a fundamental discovery in the limitations of the mathematizing power of Homo Sapiens has been made”. (Post [41], p. 105) That claim has been frequently contrasted with, if not opposed to Godel’s view that these results do not imply “any bounds for the powers of human reason, but rather for the potentialities of pure formalism in mathematics”. (Godel [26], p. 370) The dramatic fashion in which Post presents his claim almost begs for such an interpretation; it suggests, furthermore, he would have agreed with Church and Kleene judging Godel’s search for “humanly effective but non-mechanical procedures” as a fruitless pursuit.

If the “limitations” position were the only one Post had on the matter, then the above interpretation would stand without question. However, Post’s position is more complex and evolving in his work. In the first part of this paper we describe Post’s 1921 solution of the flniteness problem for the sentential logical part of Principia Mathematica. That was presented in (Post [38]) indicating also a generalization of the project with the explicit goal of obtaining a decision procedure for all of Principia Mathematica. In the second part, we use Post’s Anticipation paper [47] to follow his work in the early 1920s in pursuit of this goal: different canonical systems are formulated and shown to be equivalent to normal ones. The results of this work and his experience with the tag problem led Post to a complete reversal of his project. However, that required accepting what Davis called, Post’s Thesis; the path to that thesis is described in the third part. The fourth part gives an account of Post’s anticipation of the undecidability and incompleteness results due to Church, Turing, and Godel. Post concludes from his version of the incompleteness theorem that mathematical thinking is, and must be, creative; we explore here how Post’s notion can be understood. Finally, Post’s sustained reflections on inescapable limitations of mathematical thinking and natural laws, as well as on symbolic logics and flnitary constraints allow us to find convincing reasons why he did [not] have Turing’s Thesis. That is the topic of the final three parts.

 
Source
< Prev   CONTENTS   Source   Next >