David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
History and Philosophy of Logic 4 (1-2):203-220 (1983)
The purpose of this article is to examine aspects of the development of the concept and theory of computability through the theory of recursive functions. Following a brief introduction, Section 2 is devoted to the presuppositions of computability. It focuses on certain concepts, beliefs and theorems necessary for a general property of computability to be formulated and developed into a mathematical theory. The following two sections concern situations in which the presuppositions were realized and the theory of computability was developed. It is suggested in Section 3 that a central item was the problem of generalizing Gödel's incompleteness theorem. It is shown that this involved both the characterization of recursiveness and the attempt to clarify and formulate the notion of an effective process as it relates to the syntax of deductive systems. Section 4 concerns the decision problems which grew from the Hilbert program. Section 5 is devoted to the development of an informal' technique in the theory of computability often called ?argument by Church's thesis?
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
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
Alonzo Church (1956). Introduction to Mathematical Logic. Princeton, Princeton University Press.
Alonzo Church (1944). Introduction to Mathematical Logic. London, H. Milford, Oxford University Press.
John Corcoran, William Frank & Michael Maloney (1974). String Theory. Journal of Symbolic Logic 39 (4):625-637.
Martin Davis (ed.) (1965/2004). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions. Dover Publication.
Citations of this work BETA
No citations found.
Similar books and articles
Wilfried Sieg (1997). Step by Recursive Step: Church's Analysis of Effective Calculability. Bulletin of Symbolic Logic 3 (2):154-180.
Herbert B. Enderton (2011). Computability Theory: An Introduction to Recursion Theory. Academic Press.
Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. Cambridge University Press.
George Boolos, John Burgess, Richard P. & C. Jeffrey (2007). Computability and Logic. Cambridge University Press.
Stewart Shapiro (1980). On the Notion of Effectiveness. History and Philosophy of Logic 1 (1-2):209-230.
E. Börger (1989). Computability, Complexity, Logic. New York, N.Y., U.S.A.Elsevier Science Pub. Co..
Steve Awodey, Lars Birkedal & Dana Scott, Local Realizability Toposes and a Modal Logic for Computability.
Robert I. Soare (1996). Computability and Recursion. Bulletin of Symbolic Logic 2 (3):284-321.
Added to index2010-08-10
Total downloads12 ( #137,616 of 1,140,039 )
Recent downloads (6 months)1 ( #157,514 of 1,140,039 )
How can I increase my downloads?