Sunday, July 25, 2010

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

Finally, after doing so much work, the reader may enter the recreational field presented in the Epilogue to Part 4 (here in pdf). There he may dive into the discrete world of John Horton Conway's (game of) Life. Life is governed by three simple rules and unpredictable in exactly the same way as the behavior of a universal Turing program. It is a recursive universe under Church's thesis but nevertheless a marvelous, funny place, crowded by strange objects, moving, fighting and self-reproducing creatures, and even universal computers!

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

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 ( 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 shows. In 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, quite a few involving fundamental physical laws. Finally, (un-)provability and refutability of Church's thesis are discussed in Section In a brief resumé is presented.

The Debate about Church's Thesis and its Converse: Four Related Theses (Part 4.1 of Effective Versus Algorithmic Computability)

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?

Friday, July 16, 2010

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

Thursday, July 15, 2010

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   Syntax   Semantics  
3.5.2      Simulations of P in T5, T5 in T4, and T4 in P

Classical Computability Theory - Part 2 (of 3)

(Part 2)
This part is concerned with functions definable on arguments which are themselves the indices of an effective enumeration of programs. To this end we provide in detail an effective bijection from the set of register programs to N in Section 2.1.
In 2.2 it is proved that a noneffective bijection from the set of partially register program computable functions to N exists, and that there must exist total number-theoretic functions which are not register program computable. Sections 2.1 - 2-2 here in pdf-Format.
Two kinds of arguments known under the name 'proof by Church's thesis' are introduced in Section 2.3 (here in pdf-Format). First, the use of the thesis for maintaining absolute unsolvability results is treated, including the famous halting predicates. Second, the use of the thesis for the purpose of avoiding tedious proofs is critically commented.
In Section 2.4 three of the most important results in recursion theory are proved, namely (i) the existence of a universal register program which partially computed each n-ary register program computable function (Universality Theorem); (ii) the fact that there is a register program for effectively deciding whether an arbitrary register program eventually halts after some given number of steps (Step-counter Theorem), and (iii) Kleene's famous Normal Form Theorem, saying that each (partial) recursive function can be written in a certain form by means of only p.r. functions and only one application of the µ-operator. It follows that the (partial) recursive are exactly the (partially) register program computable functions. It is also shown that the partial recursive functions may be defined inductively with unbounded minimization restricted to total functions only!
In Section 2.5 the concepts of 'register program (recursive) enumerability' and 'partial decidability' of relations are introduced. Quite a few basic results involving these concepts are proved, e.g. the existence of nonrecursive but recursively enumerable relations, and the Enumeration Theorem for recursively enumerable sets.
Section 2.6 provides a survey of some important recursively decidable problems of recursion theory. These results are easily derived with the help of some prominent theorems: Parameter Theorem, Kleene's Second Recursion Theorem, Fixed Point Theorem, and Rice's Theorem. Sections 2.4 - 2.6 here in pdf-Format.

Finally, it should be well noted that most of the technical details of parts 2 (and 3) are based on the textbooks of Davis and Weyuker [1983] and Cutland [1980], both dealing with register programs and very recommendable.

2             Computations on program numbers (indices)

2.1          Effective denumerability of the set of register programs
2.2          Effective denumerability of the class of partially R-computable functions

2.3          What is a "proof by Church's thesis"?
2.3.1       Typical arguments for the existence of (absolutely) unsolvable problems
                in mathematics - the halting problems for register programs
2.3.2       Avoidable use of Church's thesis

2.4          Universal functions, register programs, and Kleene's Normal Form Theorem
2.5          Recursively enumerable relations and partial decidability
2.6          Parameter Theorem, Second Recursion Theorem, Fixed Point Theorem,
               and Rice's Theorem

Classical Computability Theory Part 1 (of 3)

(Part 1)

After some introductory historical remarks, the theory of primitive recursive (p.r.) functions is presented rather in detail (1.1). An inductive definition, similar to the one of Gödel [1931], is given first (1.1.1). Some simplifications of the schemata PR and CN are derived in Sections 1.1.2 – 1.1.3. Primitive recursiveness of functions is extended to sets and relations in Section 1.1.4. In 1.1.5 it is shown that the common techniques of bounded mini- and maximization for defining number theoretical notions does not lead out of the class of p.r. functions. In 1.1.6 it is shown that various more powerful-seemingly operations do not lead out of this class, too - simultaneous primitive recursion, course-of-values recursion and iteration. Additional results of this sort are mentioned – recursion in which substitutions are made for parameters, multivariable recursion (e.g. ordinary double recursion), nested simple recursion, and bounded nested recursion. In each of the sections already mentioned a lot of examples are provided. In Section sort of scale functions are introduced. 9 of 10 facts about them are proved.
In it is proved that these functions grow (in a certain defined sense) faster than any p.r. function. This must give us a hint that these computable functions are essentially different to the p.r. ones. Additionally it is sketched how to use them to obtain the so-called Grzegorczyk-hierarchy of the p.r. functions, thereby introducing the concepts of bounded primitive recursion and of elementary functionSections 1.1.1 - 1.1.7 here in pdf-Format.

Section 1.2 deals with computable functions "beyond the p.r. limit". In 1.2.1 a simple variant A of Ackermann's original function is defined by means of the scale functions and it is shown by a diagonal argument that A cannot be p.r. (A is called 'Ackermann-Péter-Robinson function' due to Péter's and Robinson's simplifications of Ackermann's original function.) In Section 1.2.2 two of the most important concepts of recursion and computability theory are introduced: arithmetization and diagonalization of function classes. Arithmetization of a (countable) set is accomplished by carrying out a Gödel-numbering (or effective encoding). Then it is shown how to encode effectively the class of p.r. functions in order to define a computable diagonal function leading out of this class. This is done in Section In the multiply recursive functions are introduced, i.e. the functions obtained by n-fold nested recursion. It is sketched how to proceed the Grzegorczyk-hierarchy by successively adding n-fold nested recursion schemata. So what we finally obtain along these lines is an infinite union of effectively computable total functions. And the question remains – do we already have all the computable functions?

In Section 1.2.3, finally, the possibilities of introducing the operation of unbounded minimization (or the µ-operator) are discussed. The distinction between unbounded minimization and regular unbounded minimization defines the difference between the sets of partial µ-recursive and µ-recursive functions. That is, by the introduction of the unrestricted µ-operator one drops the requirement for computable functions to be totally defined. This is certainly a paradigmatic change and its importance for the further development of computability is remarkable. Finally it is proved that the function A can be obtained by regular minimization (such that it is µ-recursive). Section 1.2 here in pdf-Format.

Section 1.3 deals with an alternative characterization of the p.r. functions, namely the so-called Loop programs. Syntax and semantics of these programs are provided in detail (Section 1.3.1). First examples are given in 1.3.2 and the technical basis for the use of macros is given in 1.3.3. In Section 1.3.4 it is proved that every p.r. function can be computed by some Loop program (with many additional examples), while in Section 1.4 the converse is shown by an elegant proof using simultaneous primitive recursion. Sections 1.3 - 1.4 here in pdf-Format.

Ad Section 1.5 (here in pdf-Format): After some introductory historical remarks on Gödel's general recursive functions, the sets of recursive and partial recursive functions are introduced by inductive definitions in 1.5.1, and some basic result are proved.
Section 1.5.2 is devoted to an alternative characterization of (partial) recursive functions, namely register programs (or Shepherdson-Sturgis machines). Syntax, semantics and the use of macros is treated in – In – many examples are exhibited and it is proved that the (partial) recursive functions are all computable by register programs.

1            Computations on positive integers

1.1          Primitive recursive functions

1.1.1       An inductive definition of the primitive recursive functions
1.1.2       The problem of avoiding 0-ary functions
1.1.3       Some derived substitution and primitive recursion schemata
1.1.4       Primitive recursive sets, relations, and predicates
1.1.5       Bounded mini- and maximization
1.1.6       Some extended primitive recursion schemata
1.1.7       The scale functions    Ten facts about the scale functions    The scale functions dominate the primitive recursive functions

1.2          Effectively computable functions, not primitive recursive
1.2.1       The Ackermann-Péter-Robinson function A
1.2.2       Arithmetization and diagonalization of function classes    A non primitive recursive diagonal function    Multiply recursive functions
1.2.3       Unbounded minimization – a step to partial recursive functions

1.3          Loop programs
1.3.1       The programming language    The syntax of L    The semantics of L
1.3.2       First examples of loop programs
1.3.3       The use of macros in L
1.3.4       Further examples and theorems
1.4          The class of L-computable functions is exactly the class of primitive
               recursive Functions

1.5          Recursive and partial recursive functions
1.5.1       An inductive definition of the partial recursive functions
1.5.2       Register programs    The programming language R The syntax of R The semantics of R    The use of macros in R    Each primitive recursive function is R-computable    Further examples and theorems

Classical Computability - Preliminaries and Notation

Here's everything concerning notation, abbreviations, definitions used in this text about classical computability theory, including some basic presupposed results: Preliminaries and Notation in pdf.
Note that the schemes of Composition (CN) and Primitive Recursion (PR) are defined for partial (not necessarily total) number-theoretic functions from the outset and therefore might look significantly different to what one finds in computability textbooks.