On a complexity-based way of constructivizing the recursive functions

Studia Logica 49 (1):133 - 149 (1990)
  Copy   BIBTEX


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.



    Upload a copy of this work     Papers currently archived: 74,310

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

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


Added to PP

31 (#373,554)

6 months
1 (#415,900)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Frederick Kroon
University of Auckland

Citations of this work

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

Add more citations

References found in this work

From Mathematics to Philosophy.Hao Wang - 1974 - London and Boston: London.
A Survey of Mathematical Logic.Georg Kreisel - 1966 - Philosophical Review 75 (2):240-244.
A Hierarchy of Primitive Recursive Functions.J. P. Cleave - 1963 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 9 (22):331-346.
A Hierarchy of Primitive Recursive Functions.J. P. Cleave - 1963 - Mathematical Logic Quarterly 9 (22):331-346.

View all 7 references / Add more references