Reflections on Church’s thesis.

*(English)*Zbl 0649.03001The author reports and discusses some points from J. C. Webb [Mechanism, mentalism and metamathematics. An essay on finitism (1980; Zbl 0454.03001)]. He first presents an easy argument according to which, assuming the completeness of a system F such as Gödel considered, one would obtain a contradiction to Church’s thesis. He then reports that “In fact, historically, beginning immediately after Curch’s thesis became public, Kleene used Church’s thesis to give proofs of Gödel’s incompleteness theorem.”

His second subject is the following: “One sometimes encounters statements asserting that Gödel’s work laid the foundation for Church’s and Turing’s results, as for example in Webb [loc. cit., p. 16, lines 6- 7]. It seems to me that the truth is that Church’s approach through \(\lambda\)-definability and Turing’s through his machine concept had quite independent roots (motivations), and would have led them to their main results even if Gödel’s paper “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I” [Monatsh. Math. 38, 173-198 (1931; Zbl 0002.00101)] had not already appeared.”

Kleene finally addresses an argument reporeted by Webb [loc. cit., p. 222]: “Gödel...objects that Turing ‘completely disregards’ that

(G) ‘Mind in its use, is not static, but constantly developing’.

...Gödel granted that

(F) The human computer is capable of only finitely many internal (mental) states.

holds ‘at each stage of the mind’s development’, but says that

(G)’ ‘...there is no reason why this number [of mental states] should not converge to infinity in the course of its development.”’

Kleene’s point is: “I reject that (G)’ could have any bearing on what number-theoretic functions are effectively calculable. (Indeed, Webb so argues)”. This is elaborated in some detail.

His second subject is the following: “One sometimes encounters statements asserting that Gödel’s work laid the foundation for Church’s and Turing’s results, as for example in Webb [loc. cit., p. 16, lines 6- 7]. It seems to me that the truth is that Church’s approach through \(\lambda\)-definability and Turing’s through his machine concept had quite independent roots (motivations), and would have led them to their main results even if Gödel’s paper “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I” [Monatsh. Math. 38, 173-198 (1931; Zbl 0002.00101)] had not already appeared.”

Kleene finally addresses an argument reporeted by Webb [loc. cit., p. 222]: “Gödel...objects that Turing ‘completely disregards’ that

(G) ‘Mind in its use, is not static, but constantly developing’.

...Gödel granted that

(F) The human computer is capable of only finitely many internal (mental) states.

holds ‘at each stage of the mind’s development’, but says that

(G)’ ‘...there is no reason why this number [of mental states] should not converge to infinity in the course of its development.”’

Kleene’s point is: “I reject that (G)’ could have any bearing on what number-theoretic functions are effectively calculable. (Indeed, Webb so argues)”. This is elaborated in some detail.

Reviewer: H.Schwichtenberg