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: Church's Definition/Thesis and its Epistemological Status (Part 4.2 of Effective Versus Algorithmic Computability)

Part 4.2 available in pdf-format.

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)

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?

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

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

Classical Computability Theory - Bibliography

Classical Computability Theory - Bibliography (here as pdf)


In quoting from any paper reprinted and/or translated in Davis [1965], Epstein and Carnielli
[1989], Ewald [1996], van Heijenoort [1967], and Wang [1970], and others, page numbers
are taken from those books.


Ackermann, W.
[1928] "On Hilbert's construction of the real numbers", in van Heijenoort [1967], 495-
507. (English translation of "Zum Hilbertschen Aufbau der reellen Zahlen",
Mathematische Annalen 99 (1928), 118-33.)

Agazzi, Evandro and Darvas,György (eds.)
[1997] Philosophy of Mathematics Today, Kluwer Academic Publishers, Dordrecht,
Boston, London, 1997.

Arbib, Michael A.
[1987] Brains, Machines, and Mathematics (2nd ed.), Springer Verl., New York, 1987.

Barwise J. and Keisler H. J. and Kuner K. (eds.)
[1980] The Kleene Symposium, North-Holland, 1980.

Beeson, Michael J.
[1985] Foundations of Constructive Mathematics, Springer Verl., New York, 1985.
[1988] "Computerizing mathematics: logic and computation", in Herken [1988], 91-225).

Bencivenga, Ermanno
[1987] Die Referenzproblematik – Eine Einführung in die Analytische Sprachphilosophie,
Peter Lang, Frankfurt am Main, New York, 1987.

Berg, Jonathan and Chihara, Charles
[1975] "Church's thesis misconstrued", Philosophical Studies, 28(1975), 357-62.

Berlekamp, Elwyn R. and Conway, Horton, and Guy, Richard K.
[1982] Winning Ways Vol. II, Academic Press, London, 1982.

Börger, Egon and Grädel, Erich and Gurevich, Yuri (eds.)
[1997] The Classical Decision Problem, Springer, Berlin, 1997.

Börger, Egon
[1992] Berechenbarkeit, Komplexität, Logik: Eine Einführung in Algorithmen,
Sprachen und Kalküle unter besonderer Berücksichtigung ihrer Komplexität,
(3rd ed.), Vieweg, Braunschweig, 1992.
[1980] "Entscheidbarkeit", in Speck [1980], 159-60.

Boolos, George and Jeffrey, Richard C.
[1989] Computability and Logic, (3rd ed.), Cambridge University Press, Cambridge,1989.

Borga, Marco
[1997] "From certainty to fallibility in mathematics?", in Aggazzi et al. [1997], 39-47.

Born, Rainer
[1988] "Hofstadter, Turing und die künstliche Intelligenz: Ein Strauß von Problemen",in Leidlmair and Neumaier [1988], 9-39.

Boucher, Andrew
[1997] "Parallel Machines", in Minds and Machines, 7(1997), 543-51.

Bowie, G. Lee
[1973] "An argument against Church's thesis", in The Journal of Philosophy, 70(1963),66-76.

Brady, Allen H.
[1988] "The busy beaver game and the meaning of life", in Herken [1988], 259-77.

Brauer, Wilfried and Indermark, Klaus
[1986] Algorithmen, Rekursive Funktionen und Formale Sprachen, Bibliographisches
Institut AG, Mannheim, 1986.

Bridges, Douglas S.
[1994] Computability: A Mathematical Sketchbook, Springer, New York, 1994.

Bringsjord, Selmer
[1998] "The narrational case against Church's thesis",
[http://www.rpi.edu/~brings/SELPAP/CT/ct/ct.html]

Buck, R.C.
[1963] "Mathematical induction and recursive definitions", The American Mathematical Monthly 70
(1963), 128-35.

Casti, John L.
[1996] Die Großen Fünf - Mathematische Theorien, die unser Jahrhundert prägten. Birkenhäuser, Basel, Boston, Berlin, 1996.

Church, Alonzo
[1936a] "An unsolvable problem of elementary number theory", American Journal of
Mathematics 58 (1936), 345-63. Reprinted in Davis [1965], pp. 89-107.
[1936b] "A note on the Entscheidungsproblem", Journal of Symbolic logic 1 (1936),
40-41. Reprinted in Davis [1965], 110-15.
[1956] Introduction to Mathematical Logic, Princton University Press, New Jersey,
1956.

Chaitin, Gregory J.
[1970] "On the difficulty of computations", in Chaitin [1990], 20-8.
[1974] "Information-theoretic computational complexity", in Chaitin [1990] , 29-38.
[1975] "Randomness and mathematical proof", in Chaitin [1990], 3-13.
[1976] "Information-theoretic characterizations of recursive strings", in Chaitin
[1990], 203-6.
[1988] "Randomness in arithmetic", in Chaitin [1990], 14-19.
[1990] Information, Randomness & Incompleteness - Papers on Algorithmic Information Theory, (2nd. ed.), World Scientific, Singapore, New Jersey, London, 1990.

Chomsky, Noam
[1965] Aspekte der Syntax-Theorie, (2nd ed.), Suhrkamp, Frankfurt am Main, 1983.

Cleland, C. E.
[1993] "Is the Church-Turing thesis true?", Minds and Machines 3 (1993), 283-312.
[1995] "Effective procedures and computable functions", Minds and Machines 5(1995), 9-23.

Cohen, Daniel E.
[1987] Computability and Logic, Horwood, Chichester, 1987.

Copeland, B. Jack
[1996] "The Church-Turing thesis", in Perry, J., and Zalta, E. (eds.), The Stanford
Encyclopaedia [http://plato.stanford.edu], 1996.
[1998] "Turing's O-machines, Searle, Penrose and the brain", Analysis, 58 (1998),
128-138.
[1999] "Beyond the Turing machine", Australasian Journal of Philosophy, 77 (1999), 46-67.

Cutland, Nigel
[1980] Computability - An Introduction to Recursive Function Theory, Cambridge
University Press, Cambridge, 1980.

Dahlhaus, Elias and Makowsky, Johann A.
[1988] "Gandy's principles for mechanisms as a model of parallel computation", in
Herken [1988], 309-14.

Dalla Chiara, Maria L. and Doets, Kees and Mundici, Daniele and Van Bentham, Johen (eds.)
[1997] Logic and Scientific Methods, Volume One of the Tenth International Congress
of Logic, Methodology and Philosophy of Science, Florence, August 1995,
Kluwer Academic Publishers, Dordrecht, Boston, London, 1997.

Davis, Martin D. (ed.)
[1965] The Undecidable - Basic Papers on Undecidable Propositions, Unsolvable
Problems and Computable Functions, Raven Press, New York, 1965.
[1982] "Why Gödel didn't have Church's thesis", Information and Control 54 (1982), 3-24.
[1988] "Mathematical logic and the origin of modern computers", in Herken [1988], 149-174).
[1988*] "Influences of mathematical logic on computer science", in Herken [1988], 315-26.

Davis, Martin D. and Weyuker, Elaine J.
[1983] Computability, Complexity, and Languages: Fundamentals of Theoretical
Computer science (1st edition), Academic Press, New York, 1983. For the 2nd edition click here

Dedekind, Richard
[1888] "Was sind und was sollen die Zahlen?", in Ewald [1996], 796-833. (English
translation of "Was sind und was sollen die Zahlen?", Braunschweig, 1888.

Denning, Peter J. and Dennis, Jack B. and Qualitz, Joseph E.
[1978] Machines, Languages, and Computation, Prentice Hall, New York, 1978.

Deutsch, David
[1985] "Quantum theory, the Church-Turing principle and the universal quantum
computer", The Clarendon Laboratory, University of Oxford, Oxford 0X1
3PU, UK, available on Deutsch's home page
[http://www.qubit.org/resource/news.html.] which does not exist anymore.
(Originally published in Proceedings of the Royal Society of London, A 400(1985), 97-117.)
[1996] Die Physik der Welterkenntnis - Auf dem Weg zum universellen Verstehen,
Birkenhäuser, Basel, Boston, Berlin, 1996.

Doyle, Jon
[1982] "What is Church's thesis? An outline", Laboratory for Computer Science, MIT,

Edis, Taner
[1998] "How Gödel's theorem supports the possibility of machine intelligence", Minds
and Machines 8 (1998), 252-62.

Ebbinghaus, Heinz-Dieter and Vollmer Gerd (eds.)
[1992] Denken Unterwegs – Fünfzehn metawissenschaftliche Exkursionen, S. Hinzel,
Stuttgart, 1992.

Ebbinghaus, Heinz-Dieter
[1970] "Turing-Maschinen und berechenbare Funktionen I: Präzisierung von Algorithmen",
in Jacobs [1970],1-20.

Epstein, Richard L. and Carnielli, Walter A.
[1989] Computability: Computable Functions, Logic, and the Foundations of
Mathematics, Wadsworth & Brooks, Pacific Grove, California, 1989.

Ewald, William B. (ed.)
[1996] From Kant to Hilbert: A Source Book in the Foundations of Mathematics
Vol. I,II, Clarendon Press, Oxford, 1996.

Feferman, Solomon
[1988] "Turing in the land of O(z)", in Herken [1988], 113-147.

Felscher, Walter
[1992] Berechenbarkeit: Rekursive und programmierbare Funktionen, Springer,
Berlin, Heidelberg, New York, 1993.

Føllesdal, Dagfinn
[1980] "Semantik", in Speck [1980], Vol.3, 568-79.

Frege, Gottlob
[1884] Die Grundlagen der Arithmetik, Reclam, Stuttgart, 1987.

Gandy, Robin
[1980] "Church's thesis and principles for mechanisms", in Barwise, Keisler and Kunen [1980], 123-48.
[1988] "The confluence of ideas in 1936", in Herken [1988], 55-111.
[1992] "Human versus mechanical intelligence", in Millican and Clark [1996], 125-36.

Gabbay D. and Guenthner, F. (eds.)
[1983] Handbook of Philosophical Logic. Vol. I: Elements of Classical Logic, Reidel.
Dordrecht, Boston, Lancaster, 1983.

Galton, Antony
[1996] "The Church-Turing thesis: its nature and status", in Millican and Clark
[1996], 137-77.

Gardner, Martin
[1996] The Universe in a Handkerchief - Lewis Carroll's Mathematical Recreations,
Games, Puzzles, and Word Plays, Springer, New York, 1996.

Girard, Jean-Yves
[1987] Proof Theory and Logical Complexity Vol.I, Bibliopolis, Naples, 1987.

Gödel, Kurt
[1931] "On formally undecidable propositions of Principia Mathematica and related
Systems I", in Davis [1965], 5-38. (English translation of "Über formal
unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I",
Monatshefte für Mathematik und Physik 38 (1931), 173-98.
[1934] "On undecidable propositions of formal mathematical systems", mimeographed
lecture notes taken by Stephen Kleene and J. Barkley Rosser, in Davis[1965], 41-73).
[1946] "Remarks before the Princton Bicentennial Conference on Problems in
Mathematics", in Davis [1965], 84-8.
[1995] Unpublished Philosophical Essays, (edited by Francisko A. Rodríguez-Consuegra), Birkenhäuser Verlag, Basel, Boston, Berlin, 1995.

Goodman, Nicolas D.
[1987] "Intensions, Church's thesis, and the formalization of mathematics", Notre
Dame Journal of Formal Logic 28 (1987), 473-98.

Gramss, Tino
[1998] "The theory of quantum computation: an introduction", in Gramss et al.[1998], 141-78.

Gramss, Tino, et al.
[1998] Non-Standard Computation, Wiley-VCH, Weinheim, New York, 1998.

Hasslacher, Brosl
[1988] "Beyond the Turing machine", in Herken [1988], 417-33.

Herken, Rolf (ed.)
[1988] The Universal Turing Machine, A Half-Century Survey, Oxford
University Press, Oxford, 1988.

Hermes, Hans
[1965] Enumerability, Decidability, Computability, Springer, Berlin, 1965.
[1970] "Entscheidungsproblem und Dominospiele", in Jacobs [1970], 114-40.

Heyting, Arendt
[1959] Constructibility in Mathematics, Proceedings of the Colloquium Held at
Amsterdam, 1957, North-Holland, Amsterdam, 1959.
[1959*] "Some remarks on intuitionism", in Heyting [1959], 69-71.
[1962] "After thirty years", in Logic, Methodology, and Philosophy of Science, Proceedings
of the 1960 International Congress, Stanford Press, Stanford, 1962, 194 -7.

Hilbert, David
[1926] "On the infinite", in van Heijenoort [1969], 367-92. (English translation of
"Über das Unendliche", Math. Ann. 95 (1926), 161-90.)

Hilbert, David and Ackermann, Wilhelm
[1972] Grundzüge der theoretischen Logik, (6th edition), Springer, Berlin, Heidelberg, New York, 1972.

Hilbert, David and Bernays, Paul
[1939] Grundlagen der Mathematik Vol.II, (2nd ed.), Springer, Berlin, 1970.

Hodges, Andrew
[1983] Alan Turing – The Enigma of Intelligence, Unwin Paperbacks, London, 1985.
[1988] "Alan Turing and the Turing Machine", in Herken [1988], 3-15.

Hofstadter, Douglas R.
[1986] Gödel, Escher, Bach, Ein endloses geflochtenes Band, Klett-Cotta, Stuttgart, 1986.

Jacobs, Konrad (ed.)
[1970] Selecta Mathematica II, Springer, Berlin, Heidelberg, New York, 1970.
[1970*] "Turing-Maschinen und zufällige 0-1-Folgen", in Jacobs [1970], 141-67.

Kalmár, László
[1959] "An argument against the plausibility of Church's thesis", in Heyting [1959],72-80.

Kamitz, Reinhard
[1980] "Analyse", in Speck [1980], 12-6.

Karp, R. M. and Ramachandrian, V.
[1990] "Parallel algorithms for shared-memory machines", in Van Leeuwen [1990], 869-941.

Kearns, John T.
[1997] "Thinking machines: some fundamental confusions", Minds and Machines 7
(1997), 269-87.

Kelly, Kevin T. and Schulte, Oliver
[1997] "Church's thesis and Hume's problem", in Dalla Chiara et al. [1997], 159-77)

Kielkopf, Charles F.
[1978] "The intensionality of the predicate '__is recursive'", The Notre Dame Journal
of Symbolic Logic, 1(1978), 165-73.

Kleene, Stephen C.
[1936] "General recursive functions of natural numbers", Math. Ann. 112(1936), 727-
42. Reprinted in Davis [1965], 237-52.
[1943] "Recursive predicates and quantifiers", Trans. Am. Math. Soc. 53 (1943), 41-
73. Reprinted in Davis [1965], 255-87.
[1952] Introduction to Metamathematics, ( 5th reprint), North-Holland, Amsterdam, 1952.
[1987] "Reflectons on Church's thesis", Notre Dame Journal of Formal Logic 28(1987), 490-8.
[1988] "Turing's analysis of computability, and major applications of it", in Herken,
[1988], 17-54.

Kreisel, Georg
[1987] "Church's thesis and the ideal of informal rigour", The Notre Dame Journal of
Formal Logic 28 (1987), 499-510.

Kripke, Saul A.
[1987] Wittgenstein über Regeln und Privatsprache - Eine elementare Darstellung,
Suhrkamp, Frankfurt am Main, 1987.

Kutschera, Franz v.
[1975] Sprachphilosophie, Wilhelm Fink Verlag, München, 1975.

Leockx, Jacques
[1976] Algorithmentheorie, Springer, Berlin, Heidelberg, New York, 1976.

Li, Ming and Vitány, Paul M. B.
[1990] "Kolmogorov complexity and its applications", in Van Leeuwen [1990], 187-254.

McCarthy, Charles
[1987] "Variations on a thesis: intuitionism and computability", The Notre Dame
Journal of Formal Logic 28 (1987), 536-80.

McCarthy, Timothy and Shapiro, Stewart
[1987] "Turing projectability", The Notre Dame Journal of Formal Logic 28 (1987), 520-535.

McMullin, Ernan
[1980] "Geschichte der Wissenschaft", in Speck [1980], 737-45.

Mendelson, Elliot
[1963] "On some recent criticism of Church's thesis", The Notre Dame Journal of

Formal Logic, 3(1963), 201-5.
[1990] "Second thoughts about Church's thesis and mathematical proofs", The Journal
of Philosophy, 87(1990), 225-232.

Millican, Peter and Clark, Andy (eds.)
[1996] Machine and Thought – The Legacy of Alan Turing Vol. I, Clarendon Press, Oxford, 1996.

Moschovakis, Joan Rand
[1971] "Can there be no nonrecursive functions", The Journal of Symbolic Logic 36(1971), 309-15.

Mosterín, Jesús
[1997] "The natural numbers as a universal library", in Aggazzi and Darvas [1997],305.17.

Nelson, R. J.
[1987] "Church's thesis and cognitive science", The Notre Dame Journal of Formal Logic 28 (1987), 581-614.

Neumaier, Otto
[1988] "Über Wittgenstein über Turing über künstliche Intelligenz", in Leidlmair and
Neumaier [1988], 79-90.

Nørretranders, Tor
[1997] Spüre die Welt – Die Wissenschaft des Bewusstseins, Rohwolt, Hamburg, 1997.

Odifreddi, Piergiorgio
[1989] Classical Recursion Theory, The Theory of Functions and Sets of Natural Numbers, North-Holland, Amsterdam, New York, 1989.
[1996] "Kreisel's Church", in Odifreddi, P. (ed.), Kreiseliana, About and Around Georg Kreisel, AK Peters. Wellesly MA, 1996.

Padberg, Friedhelm
[1991] Elementare Zahlentheorie, (2. Aufl.), BI-Wiss.-Ver. Mannheim, Wien, Zürich, 1991.

Parsons, Charles
[1997] "What can we do "in principle"?", in Dalla Chiara et al. [1997], 325-54.

Pellizzari, Thomas
[1998] "Quantum Computers: first steps towards a realzation", in Gramss et al.[1998], 179-210.

Penrose, Roger
[1988] "On the physics and mathematics of thought", in Herken [1988], 492-522.

Péter, Rózsa
[1935] "Konstruktion nichtrekursiver Funktionen", Math. Ann. 111 (1935), 42-60.
[1936] "Über die mehrfache Rekursion", Math. Ann. 113 (1936), 489-527.
[1959] "Rekursivität und Konstruktivität", in Heyting [1959], 226-33.
[1967] Recursive Functions, (3rd ed.), Academic Press, New York, 1967.

Pierce, Charles Sanders
[1881] "On the logic of number", Am. J. Math. 4 (1881), 85-95. Reprinted in Ewald [1996], 596-608.

Post, Emil L.
[1936] "Finite combinatory processes - formulation 1", The Journal of Symbolic
Logic 1(1936), 103-5.
[1943] "Recursively enumerable sets of positive integers and their decision problems",
Am. Math. Soc. 50 (1944), 284-316. Reprinted in Davis [1965], 305-37.
[1947] "Recursive unsolvability of a problem of Thue", The Journal of Symbolic
Logic 12 (1947), 1-11. Reprinted in Davis [1965], 293-303.
[1965] "Absolutely unsolvable problems and relatively undecidable propositions, Account
of an anticipation", in Davis [1965], 340-433.

Poundstone, William
[1985] The Recursive Universe - Cosmic Complexity and the Limits of Scientific
Knowledge, Oxford University Press, Oxford, 1985.

Quine, Willard Van Orman
[1960] Wort und Gegenstand, Reclam, Stuttgart, 1980.
[1969] Ontologische Relativität und andere Schriften, Reclam, Stuttgart, 1975.

Richman, Fred
[1981] "Church's thesis without tears", The Journal of Symbolic Logic 48 (1981), 797-
803.

Robinson, Raphael M.
[1947] "Primitive recursive functions", Bull. Am. Math. Soc. 53 (1947), 925-42.

Rosen, Robert
[1988] "Effective Processes and Natural Law", in Herken [1988], 523-37.

Ross, David
[1974] "Church's thesis: what its difficulties are and are not", The Journal of
Philosophy, 15(1974), 515-25.

Rosser, J. B.
[1939] "An informal exposition of proofs of Gödel's theorem and Church's theorem",
in Davis [1965], 223-35.

Rucker, Rudy
[1990] Der Ozean der Wahrheit, Über die logische Tiefe der Welt, Fischer, Frankfurt
am Main, 1990. (The original title is Mind Tools, Houghton Mifflin Company, Boston, 1987.)

Schnelle, Helmut
[1988] "Turing naturalized: Von Neumann's unfinished project", in Herken [1988],
539-59.

Schnorr, Claus Peter
[1974] Rekursive Funktionen und ihre Komplexität, Teubner, Stuttgart, 1974.

Schöning, Uwe
[1995] Theoretische Informatik – kurzgefasst, Spektrum Akademischer Verl., Heidelberg,
1995.

Schulz, Klaus-Dieter
[1997] Die These von Church - Zur erkenntnistheoretischen und sprachphilosophischen
Bedeutung der Rekursionstheorie, Lang, Frankfurt am Main, 1997.

Searle, John R.
[1996] Die Wiederentdeckung des Geistes, Suhrkamp, Frankfurt am Main, 1996.

Shagrir, Oron
[1997] "Two dogmas of Computationalism", Minds and Machines 7(1997), 321-44.

Shanker, S. G.
[1987] "Wittgenstein versus Turing on the nature of Church's thesis", The Notre Dame
Journal of Formal Logic 28 (1987), 615-49.

Shepherdson, John C.
[1988] "Mechanisms for computing over arbitrary structures", in Herken [1988], 581-601.

Shepherdson, John.C. and Sturgis, H.E.
[1963] "Computability of recursive functions", J. Assoc. Computing Machinery 10
[1963], 217-55.

Sieg, Wilfried
[1992] "Turings Problem oder: die Mechanisierung mathematischer Erfahrung", in
Ebbinghaus and Vollmer [1992], 137-52.

Skolem, Thoralf
[1923] "The foundations of elementary arithmetic established by means of the recursive
mode of thought, without the use of apparent variables ranging over infinite
domains", in van Heijenoort [1967], 302-33. English translation of "Begründung
der elementaren Arithmetik durch die rekurrierende Denkweise ohne
Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich",
Videnskaps Akademi i Kristiana (Math. Naturv. Klasse) Skrifter No. 6(1923), pp.38.

Smith, Einar
[1996] Elementare Berechenbarkeitstheorie, Springer, Berlin, 1996.

Smullyan, Raymond
[1988] Forever Undecided – A Puzzle Guide to Gödel, Oxford University Press,
Oxford, New York, Toronto, 1988.

Soare, R. I.
[1997] "Computabiity and enumerability", in Dalla Chiara et al. [1997], 221-37.

Speck, Josef (ed.)
[1980] Handbuch wissenschaftstheoretischer Begriffe, (3 vols.), Vandenhoeck &
Ruprecht, Göttingen, 1980.

Suppes, Patrick
[1957] Introduction to Logic, Van Nostrand Reinhold Company, NewYork, 1957.
[1960] Axiomatic Set Theory, Van Nostrand Company, Princton, 1960.
[1980] "Definition", in Speck [1980], 124-29.

Tait, William W.
[1981] "Finitism", The Journal of Philosophy 78 (1981), 524-47.

Tamburrini, Guglielmo
[1997] "Mechanistic theories in cognitive science: the import of Turing's thesis", in
Dalla Chiara et al. [1997], 239-57.

Thomas, William J.
[1979] "A simple generalization of Turing computability", The Notre Dame Journal
of Formal Logic 20 (1979), 95-102.

Turing, Alan
[1936] "On computable numbers, with an application to the Entscheidungsproblem",
Proc. Lond. Math. Soc. (ser. 2) 42 (1936), 230-265. Reprinted in Davis [1965],115-51.
[1939] "Systems of logic based on ordinals", Proceedings of the London Mathematical
Society (ser.2), 45(1939), 161-228. Reprinted in Davis [1965], 155-222.
[1950] "Computing machinery and intelligence", [wysiwyg://57/http://www.abelard.
org/turpap/turpap.htm]. First puplished in Mind 10 (1950), 433-60.

Truss, J. K.
[1991] Discrete Mathematics for Computer Scientists, Addison & Wesley, New York,
1991

Van Dalen, D.
[1983] "Algorithms and decision problems: a crash course in recursion theory", in
Gabbay and Guenthner [1983], 409-78.

Van Dalen, D. andDoets, H.C. and de Swart, H.
(1978) Sets: Naive, Axiomatic and Applied, Pergamon Press, Oxford, New York,
1978.

Van Dantzig, D.
[1956] "Is 101010 a finite number?" in Dialectica, 9(1956), 273-77.
Reprinted in Epstein and Carnielli [1989], 258-61.

Van Emde Boas, P.
[1990] "Machine models and simulations", in Van Leeuwen [1990], 3-66.

van Hejenoort, J. (ed.)
[1967] From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931,
Harvard University Press, Cambridge MA, 1967.
online: amazon, google books

Van Leeuwen, Jan (ed.)
[1990] Handbook of Theoretical Computer Science – Volume A: Algorithms and
Complexity, Elsevier Science Publishers, Amsterdam, New York, 1990.

Wang, Hao
[1970] Logic, Computers, and Sets, Chelsea Publishing Company, New York, 1970.
[1989] Computation, Logic, Philosophy, A Collection of Essays, Science Press and
Kluwer Academic Publishers, Bejing, Dordrecht, 1990.

Weingartner, Paul
[1976] Wissenschaftstheorie II.1, Grundlagenprobleme der Logik und Mathematik,
Frommann-Holzboog, Stuttgart, 1976.
[1978] Wissenschaftstheorie I - Einführung in die Hauptprobleme (2nd ed.),
Frommann-Holzboog, Stuttgart, 1978.
[1980] "Wahrheit", in Speck [1980], 680-89.

Wittgenstein, Ludwig
[1984] Wittgenstein und der Wiener Kreis, Suhrkamp, Frankfurt am Main, 1984.
[1989] Vorlesungen 1930-1935, Suhrkamp, Frankfurt am Main, 1989.

Yasuhara, Ann
[1971] Recursive Function Theory & Logic, Academic Press, New York, 1971.