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.