Graduate studies at Western
History and Philosophy of Logic 26 (2):93-113 (2005)
|Abstract||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)|
|Through your library||Configure|
Similar books and articles
Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
Janet Folina (1998). Church's Thesis: Prelude to a Proof. Philosophia Mathematica 6 (3):302-323.
John T. Kearns (1997). Thinking Machines: Some Fundamental Confusions. [REVIEW] Minds and Machines 7 (2):269-87.
Tim Button (2009). Sad Computers and Two Versions of the Church–Turing Thesis. British Journal for the Philosophy of Science 60 (4):765-792.
Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW] Minds and Machines 18 (3):349-355.
Nachum Dershowitz & Yuri Gurevich (2008). A Natural Axiomatization of Computability and Proof of Church's Thesis. Bulletin of Symbolic Logic 14 (3):299-350.
Robin Gandy (1980). Church's Thesis and Principles for Mechanisms. In The Kleene Symposium. North-Holland.
Robert Black (2000). Proving Church's Thesis. Philosophia Mathematica 8 (3):244--58.
Stephen C. Kleene (1987). Reflections on Church's Thesis. Notre Dame Journal of Formal Logic 28 (4):490-498.
Maía Manzano (1997). Alonzo Church:His Life, His Work and Some of His Miracles. History and Philosophy of Logic 18 (4):211-232.
Added to index2010-08-10
Total downloads5 ( #170,048 of 724,062 )
Recent downloads (6 months)1 ( #61,087 of 724,062 )
How can I increase my downloads?