Sunday, July 25, 2010

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

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

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 1.1.7.1 sort of scale functions are introduced. 9 of 10 facts about them are proved.
In 1.1.7.2 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 function. Sections 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 1.2.2.1. In 1.2.2.2 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 1.5.2.1 – 1.5.2.2. In 1.5.2.3 – 1.5.2.4 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
1.1.7.1    Ten facts about the scale functions
1.1.7.2    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
1.2.2.1    A non primitive recursive diagonal function
1.2.2.2    Multiply recursive functions
1.2.3       Unbounded minimization – a step to partial recursive functions

1.3          Loop programs
1.3.1       The programming language
1.3.1.1    The syntax of L
1.3.1.2    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
1.5.2.1    The programming language R
1.5.2.1.1 The syntax of R
1.5.2.1.2 The semantics of R
1.5.2.2    The use of macros in R
1.5.2.3    Each primitive recursive function is R-computable
1.5.2.4    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.