The Debate about Church's Thesis and its Converse: Arguments Against Church's Thesis

The arguments against Church's thesis itself (the "harder" half) are treated in Section 4.4 (available here in pdf-format). Preliminaries concern the concepts of relative (or oracle) computability – including a relativized form of the thesis, and randomness of finite and infinite 0-1-sequences. Both theories are sketched by means of basic results.

The first argument ever put forward against the thesis, by the Hungarian mathematician and logician Laszlo Kalmár in 1959, is extensively discussed in Section 4.4.1. Kalmár introduced a "method" for computing a nonrecursive function with the help of carrying out what he called "proof by any correct means" – a concept for which he provided a clever and formally indubitable definition. G. Lee Bowie also argued against the more problematic half of Church's thesis. In his objection he constructed a machine which randomly selects effectively computable out of the continuum of all number-theoretic functions. The probability of getting a recursive functions this way is on most accounts 0, so is the probability of the truth of Church's thesis, Bowie concludes. His argument is treated in Section 4.4.2. The only argument not based on an obvious misunderstanding of the term 'effective' comes from the philosopher William J. Thomas. Nevertheless it seems to be based on the hidden premise that there exist one-step algorithms computing nonrecursive functions. His argument is rejected in Section 4.4.3. Selmer Bringsjord, in his internet paper [1998], argued that the set of interesting stories (!) were effectively decidable, but not recursive. (See Section 4.4.4) Anyone who finds such an approach uninteresting may immediately turn to Section 4.4.5, where the argument from machine is examined. Suppose that a mathematician invents some kind of notional "mechanism" (in the broadest sense) that can be said to compute effectively a nonrecursive function. Or suppose that one finds or proves consistent with current physics such a machine. Would this necessarily refute Church's thesis?

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.