On a complexity-based way of constructivizing the recursive functions |
| |
Authors: | F. W. Kroon W. A. Burkhard |
| |
Affiliation: | (1) Department of Philosophy, The University of Auckland, Newzealand;(2) Department of Philosophy, The Australian National University, Australia;(3) Department of Applied Physics and Information Science, University of California at San Diego, USA |
| |
Abstract: | Let gE(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(gE(m, n)=o) can be proved constructively if one can find a speedfunction ss, with s(m) bounding the number of steps for getting a value of (m), such that mns(m) s.t. gE(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.We are grateful to an anonymous referee for Studia Logica for valuable advice leading to substantial improvements in the presentation of the main definitions and theorem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|