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: 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?

Classical Computability - Part 3 (of 3) (String Computability)

(Part 3)

Purpose of this part is first to extend the formalized notions of computability to the domain of arbitrary strings of symbols of an alphabet.  In 3.1 computable bijections from alphabets A to N are introduced. These have the features of allowing homogeneous base n notations for positive integers, for all n>0 and the encoding and decoding by means of p.r. functions. Several useful properties of the coding functions are derived.

In 3.2 definitions extending the formalized computability concepts to the domain of strings are given first. Then some important string functions and relations are proved to be recursive. These are used in the subsequent sections for equivalence proofs.

In Sections 3.3 – 3.5 different kinds of string manipulating algorithms are introduced and proved equivalent, including Post-Turing programs (Section 3.4), as well as deterministic and nondeterministic quintuple and quadruple Turing programs (3.5). The operational semantics of the latter was approximated to the other languages occurring in this work. The uncomplicated equivalence proofs in 3.5.2 come from the present author. Part 3 is here in pdf-Format.





3           Computations on strings (Words)


3.1        Effective denumerability of strings
3.2        String computability


3.3        The programming languages L
3.3.1     The syntax of L
3.3.2     The semantics of L
3.3.3     Some useful macros in L
3.3.4     Simulation of R in L


3.4        The programming language P (Post-Turing programs)
3.4.1     The syntax of P
3.4.2     The semantics of P
3.4.3     Some useful macros in P
3.4.4     Simulation of L in P
3.4.5     Simulation of P in R


3.5        Deterministic and nondeterministic Turing programs
3.5.1     The programming languages T4 and T5
3.5.1.1   Syntax
3.5.1.2   Semantics  
3.5.2      Simulations of P in T5, T5 in T4, and T4 in P