David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Studia Logica 49 (1):133 - 149 (1990)
Let g E(m, n)=o mean that n is the Gödel-number of the shortest derivation from E of an equation of the form (m)=k. Hao Wang suggests that the condition for general recursiveness mn(g E(m, n)=o) can be proved constructively if one can find a speedfunction s s, with s(m) bounding the number of steps for getting a value of (m), such that mn s(m) s.t. g E(m, n)=o. This idea, he thinks, yields a constructivist notion of an effectively computable function, one that doesn't get us into a vicious circle since we intuitively know, to begin with, that certain proofs are constructive and certain functions effectively computable. This paper gives a broad possibility proof for the existence of such classes of effectively computable functions, with Wang's idea of effective computability generalized along a number of dimensions.
|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
Hao Wang (1966). A Survey of Mathematical Logic. Philosophical Review 75 (2):240-244.
Hartley Rogers (1965). Review: A. A. Mucnik, Solution of Post's Reduction Problem and of Certain Other Problems in the Theory of Algorithms. I. [REVIEW] Journal of Symbolic Logic 30 (1):90-90.
Citations of this work BETA
F. W. Kroon (1996). The Intrinsic Difficulty of Recursive Functions. Studia Logica 56 (3):427 - 454.
Similar books and articles
Carl G. Jockusch Jr & Alexandra Shlapentokh (1995). Weak Presentations of Computable Fields. Journal of Symbolic Logic 60 (1):199 - 208.
Arto Salomaa (1985). Computation and Automata. Cambridge University Press.
Rodney G. Downey & Asher M. Kach (2010). Euclidean Functions of Computable Euclidean Domains. Notre Dame Journal of Formal Logic 52 (2):163-172.
Erich Grädel & Yuri Gurevich (1995). Tailoring Recursion for Complexity. Journal of Symbolic Logic 60 (3):952-969.
Alexandra Shlapentokh (2002). Generalized Weak Presentations. Journal of Symbolic Logic 67 (2):787-819.
Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. Cambridge University Press.
Nachum Dershowitz & Yuri Gurevich (2008). A Natural Axiomatization of Computability and Proof of Church's Thesis. Bulletin of Symbolic Logic 14 (3):299-350.
Added to index2009-01-28
Total downloads10 ( #227,665 of 1,724,951 )
Recent downloads (6 months)4 ( #167,175 of 1,724,951 )
How can I increase my downloads?