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: 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.)