If you are experiencing problems downloading PDF or HTML fulltext, our helpdesk recommend clearing your browser cache and trying again. If you need help in clearing your cache, please click here . Still need help? Email help@ingentaconnect.com

Diagonalisation and Church's Thesis: Kleene's Homework

$53.91 plus tax (Refund Policy)

Buy Article:

Abstract:

In this paper we will discuss the active part played by certain diagonal arguments in the genesis of computability theory. 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)

Document Type: Research Article

DOI: http://dx.doi.org/10.1080/0144534042000271157

Affiliations: 1: Universidad Autónoma de Madrid 2: Universidad de Salamanca

Publication date: May 1, 2005

More about this publication?
Related content

Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
X
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more