The Debate about Church's Thesis and its Converse: Four Related Theses (Part 4.1 of Effective Versus Algorithmic Computability)

Part 4.1 available in pfd-format.

Section 4.1 deals with the computability theses put forward by Post, Turing, Gödel, and Gandy. Some preliminary considerations are presented in a Prologue. These thoughts concern finite and infinite symbol games, the use of infinite symbol games for simplifying undecidability proofs (by the technique called 'reduction'), and the question whether (meta-) mathematics could be regarded as (symbol) game, and whether it could be therefore seen as empirical theory dealing with physical symbol manipulation. The latter idea is supported by a recent, more naturalistic, approach to the philosophy of mathematics. Consequently, we also have to deal with the idea of Church's thesis being an empirical statement – as such it is considered by quite a few authors. Five main results are listed at the end of the Prologue.

Section 4.1.1 is devoted to the following two questions: (1) Did Post anticipate Church's and Turing's theses already in the early 1920's? (2) Which epistemological status did Post ascribe to his own and Church's proposal? Also, Post's influence on computer science and linguistics is briefly sketched. This also includes some aspects of Noam Chomsky's work. "Chomsky's thesis" is formulated as interesting (indeed empirical) analogon to Church's.

In Section 4.1.2 it is summarized how Turing managed to solve Hilbert's Entscheidungsproblem, thereby defining 'solvability' by means of his notional machines. In a short digression the "silly" question is asked who really invented "Turing computability" as presented today in every textbook. Finally, the reception of Turing's definition and analysis is critically commented. In particular, it is argued against the view of his thesis dealing with the highly vague terms 'machine' and 'mechanical'. (This topic will occur again in subsequent sections.)

In Section 4.1.3 the following questions are to be answered: (1) Did Gödel anticipate Church's definition/thesis? (2) Did Gödel accept the definition/thesis only from an extensional point of view? (3) Did Gödel accept the definition/thesis "only under a mechanistic interpretation" – as was maintained by Klaus-Dieter Schulz?

Robin Gandy's thesis and complex analysis concerning what he called 'discrete deterministic mechanical devices' is briefly sketched in Section 4.1.4. This very general physical computation model serves as contrast to other purely mathematical ones. (But note that David Deutsch's model of quantum computation is by far more general. Deutsch's interpretation of Church's thesis and his own reformulation are mentioned in the Prologue to Section 4.1.)

Finally, the Epilogue to Section 4.1 deals with the relation between Church's thesis and the various forms of AI-theses (or theses of mechanism). Can Church's thesis be used in arguments to support the dogma that the human mind/brain is some kind of "computer" (or "machine")? Conversely, can the dogma be used to support or refute the thesis?