History and Philosophy of Logic 26 (2):93-113 (2005)

María Manzano
Universidad de Salamanca
In this paper we will discuss the active part played by certain diagonal arguments in the genesis of computability theory. 1?In some cases it is enough to assume the enumerability of Y while in others the effective enumerability is a substantial demand. These enigmatical words by Kleene were our point of departure: When Church proposed this thesis, I sat down to disprove it by diagonalizing out of the class of the ??definable functions. But, quickly realizing that the diagonalization cannot be done effectively, I became overnight a supporter of the thesis. (1981, p. 59) The title of our paper alludes to this very work, a task on which Kleene claims to have set out after hearing such a remarkable statement from Church, who was his teacher at the time. There are quite a few points made in this extract that may be surprising. First, it talks about a proof by diagonalization in order to test?in fact to try to falsify?a hypothesis that is not strictly formal. Second, it states that such a proof or diagonal construction fails. Third, it seems to use the failure as a support for the thesis. Finally, the episode we have just described took place at a time, autumn 1933, in which many of the results that characterize Computability Theory had not yet materialized. The aim of this paper is to show that Church and Kleene discovered a way to block a very particular instance of a diagonal construction: one that is closely related to the content of Church's thesis. We will start by analysing the logical structure of a diagonal construction. Then we will introduce the historical context in order to analyse the reasons that might have led Kleene to think that the failure of this very specific diagonal proof could support the thesis. This is a joint paper. We have both attempted to add a small piece to an amazing historical jigsaw puzzle at a juncture we feel to be appropiate. In the paper by Manzano 1997 the aforementioned words by Kleene were quoted, and since then several logicians, Enrique Alonso first and foremost, have questioned her on this issue. Here we both submit our reply. (1999, pp. 249--273)
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1080/0144534042000271157
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 61,025
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

An Unsolvable Problem of Elementary Number Theory.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (2):73-74.
On Notation for Ordinal Numbers.S. C. Kleene - 1938 - Journal of Symbolic Logic 3 (4):150-155.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Recursive Predicates and Quantifiers.S. C. Kleene - 1943 - Transactions of the American Mathematical Society 53:41-73.

View all 14 references / Add more references

Citations of this work BETA

Visions of Henkin.María Manzano & Enrique Alonso - 2015 - Synthese 192 (7):2123-2138.

Add more citations

Similar books and articles

Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Reflections on Church's Thesis.Stephen C. Kleene - 1987 - Notre Dame Journal of Formal Logic 28 (4):490-498.
Proving Church's Thesis.Robert Black - 2000 - Philosophia Mathematica 8 (3):244--58.
SAD Computers and Two Versions of the Church–Turing Thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Church's Thesis: Prelude to a Proof.Janet Folina - 1998 - Philosophia Mathematica 6 (3):302-323.
Alonzo Church:His Life, His Work and Some of His Miracles.Maía Manzano - 1997 - History and Philosophy of Logic 18 (4):211-232.


Added to PP index

Total views
37 ( #285,311 of 2,439,602 )

Recent downloads (6 months)
2 ( #282,563 of 2,439,602 )

How can I increase my downloads?


My notes