Graduate studies at Western
Studia Logica 49 (1):133 - 149 (1990)
|Abstract||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)|
|Through your library||Configure|
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 downloads3 ( #213,863 of 739,375 )
Recent downloads (6 months)0
How can I increase my downloads?