Why Post Did [Not] Have Turing’s Thesis

Wilfried Sieg, Mate Szabo and Dawn McLaughlin

... I study Mathematics as a product of the human mind and not as absolute.

(Post in Anticipation, i.e., (Post [47], p. 64)).

Abstract The conceptual confluence of Post’s and Turing’s analysis of combinatory processes, respectively of mechanical procedures, is the central topic in Davis and Sieg’s [14]. Where Turing argued convincingly for the adequacy of his notion of machine computation in 1936, Post viewed his identical notion in the same year as being tied to a working hypothesis in need of “continual verification”. Post gave novel and informative arguments for his thesis or, as he put it, generalization. He insisted, however, that ultimately a psychological analysis “of mental processes involved in combinatory mathematical processes” has to be given. In this way, he hoped to obtain a natural law and thus the basis for the claim that the undecidability and incompleteness theorems constitute “a fundamental discovery in the limitations of the mathematizing power of Homo Sapiens”. Our detailed analysis of (the background for) his work on the issues leads to an unambiguous answer to the question Did Post have Turing’s Thesis?: He did [not].

This paper was written for Martin Davis, brilliant mathematical logician, expert computer scientist, and dedicated student of Post; his humanity and devotion to logic are transcendent.— For Wilfried Sieg, he has been a mentor and friend for more than thirty years; during the last few years we have been collaborating, e.g., organizing a session for the Turing Centenary Conference in Cambridge in 2012 and writing a joint paper, our [14]. It has been a pleasure and privilege to do so.

W. Sieg (B) • M. Szabo • D. McLaughlin Carnegie Mellon University, Pittsburgh, USA e-mail: This email address is being protected from spam bots, you need Javascript enabled to view it

M. Szabo

e-mail: This email address is being protected from spam bots, you need Javascript enabled to view it

D. McLaughlin

e-mail: This email address is being protected from spam bots, you need Javascript enabled to view it

© Springer International Publishing Switzerland 2016 175

E. G. Omodeo and A. Policriti (eds.), Martin Davis on Computability,

Computational Logic, and Mathematical Foundations,

Outstanding Contributions to Logic 10, DOI 10.1007/978-3-319-41842-1_7

 
Source
< Prev   CONTENTS   Source   Next >