On a complexity-based way of constructivizing the recursive functions

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)
DOI 10.1007/BF00401559
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 26,188
Through your library
References found in this work BETA
A Survey of Mathematical Logic.Hao Wang - 1966 - Philosophical Review 75 (2):240-244.

Add more references

Citations of this work BETA
The Intrinsic Difficulty of Recursive Functions.F. W. Kroon - 1996 - Studia Logica 56 (3):427 - 454.

Add more citations

Similar books and articles
Computation and Automata.Arto Salomaa - 1985 - Cambridge University Press.
Euclidean Functions of Computable Euclidean Domains.Rodney G. Downey & Asher M. Kach - 2010 - Notre Dame Journal of Formal Logic 52 (2):163-172.
Tailoring Recursion for Complexity.Erich Grädel & Yuri Gurevich - 1995 - Journal of Symbolic Logic 60 (3):952-969.
Generalized Weak Presentations.Alexandra Shlapentokh - 2002 - Journal of Symbolic Logic 67 (2):787-819.
Computability & Unsolvability.Martin Davis - 1958 - Dover Publications.

Monthly downloads

Added to index

2009-01-28

Total downloads

16 ( #292,930 of 2,154,061 )

Recent downloads (6 months)

1 ( #398,005 of 2,154,061 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums