The Debate about Church's Thesis and its Converse: Arguments Against the Converse of Church's Thesis (Part 4.3 of Effective Versus Algorithmic Computability)

Section 4.3 (here in pdf-format) deals with arguments that were put forward against the "easier half", the less problematic converse of Church's thesis. Note that 'effectivity' was and is a favorite term used in the constructive philosophy of mathematics. So, who wonders that the existential quantifiers occurring in the thesis have been interpreted constructively? (4.3.1) "If you cannot provide a Turing program for computing some f (though there is an elegant nonconstructive proof that such exists), you cannot compute f effectively. You cannot compute it at all!" Church anticipated such objections quite early. A detailed discussion of his "confusing" answer, given in his famous footnote 10 of [1936a], precedes Section 4.3.1.1. There, the vicious circle argument of Rosza Péter and the alleged (hardly known) counter-examples of Arendt Heyting are exhibited. Péter's argument deals with the impossibility of defining the notion "effectively computable" by means of nonconstructive existential quantifiers. Heyting's examples are finite (and therefore recursive) predicates for which we probably will never know an algorithm. Heyting's examples are rejected, as are the "excentric" examples of Sections 4.3.1.2 – 4.3.1.3. The latter additionally contains the presentation of philosopher G. Lee Bowie's argument [1974] for the intensionality of the context '…is effectively computable'. The view that the only effectively computable functions are the primitive recursive ones is discussed in Section 4.3.2. In 4.3.3 it is called in question whether a recursive function may justly be called computable in case there is not enough time and space available to calculate even small arguments, while finally, in Section 4.3.4 we ask whether it is 'effective' when we don't know whether the computation takes one day, one week, or longer than the universe exists.

The Debate about Church's Thesis and its Converse: Church's Definition/Thesis and its Epistemological Status (Part 4.2 of Effective Versus Algorithmic Computability)

Part 4.2 available in pdf-format.

Section 4.2 is devoted to the much discussed epistemological status of Church's thesis. First, (4.2.1) the thesis is introduced in the original form, namely as definition, and it is explained where the term 'Church's thesis' comes from. In 4.2.2 the arguments in favor of the thesis/definition, put forward by various authors, are exhibited and discussed. The present author doesn't want to hold back his opinion that Church's step-by-step argument remains to be the best on the market – in opposition to some recent criticism by Sieg, followed by Soare and Schulz.

The epistemological status of the thesis is further examined at full length in Section 4.2.3. After some preliminary remarks on definitions (real and nominal ones, as propositions and as rules) using Weingartner's theory of definition, the early debate among the initiators of computability theory is recollected and analyzed (4.2.3.1). Church, Turing, and Gödel pleaded for 'definition', while Post, Kleene, and Kalmár rejected this view. Already this controversy contained essentially all ingredients of later discussions, up to now. Nothing really new has been contributed since then, as Section 4.2.3.2 shows. In 4.2.3.3 the thesis is compared to other well-known mathematical theses/definitions such as that every circle is the set of all points equidistant to some given point. Also, Quines discussion of the paradigmatic case of the definition of 'ordered pair' (in Word and Object) is examined in order to find some clue what to do with Church's thesis. Further comparisons and analogies are listed in 4.2.3.4, quite a few involving fundamental physical laws. Finally, (un-)provability and refutability of Church's thesis are discussed in Section 4.2.3.5. In 4.2.3.6 a brief resumé is presented.

The Debate about Church's Thesis and its Converse: Introduction (to Effective Versus Algorithmic Computability)

Here is the Introduction in pdf-Format. Note that the page numbering continues with 263 as well as the section numbering with 4 but footnotes start again with 1; any references to section numbers smaller than 4 refer to previously posted sections of my "Classical Computability Theory". In other words, the latter is the more technical basis for what is about to come as part 4: a detailed discussion about Church's Thesis.

About the Introduction
It is attempted there to formulate Church's thesis in its fullest content. This has to be accomplished in respect to the term 'recursive' – which is not only restricted to functions on positive integers, as well as to the term 'effectively computable'. It is quoted from Church's original [1936a] in order to make it plain that his thesis deals with algorithms – the kind of strictly "mechanical" procedures mathematicians like to construct in order to convince their collegues of the computability or decidability of some function or problem. There is an informal theory of algorithms and computability. The principles of this theory are introduced and discussed in the same order as presented in Ebbinghaus [1970] Though not all of these principles may appear entirely cristal clear, the truly Church's thesis is formulated with respect to them, as dealing with algorithms in the sense of informal algorithm theory. It is then called in question whether the thesis is indeed vague – as maintained by many authors. Thereby the three most important theses of the present work are introduced. These propositions are, in brief, (i) the informal concept occurring in the antecendens of Church's thesis is, in opposition to what is usually said, not vague (or vague in some minimal sense of vagueness), (ii) Church misled the audience by redundantly introducing two termini technici, namely 'effective' and 'algorithmic computation', of which the former is associated with many different connotations, while the latter is rather unambiguous, and (iii) "algorithmicity" must not be confused with concepts like "effective", "mechanical", "constructive", "physical", "feasible" or even "human computability" (respectively, the use of the latter words is in general different to that of the former.)