ISSN:
1572-8730
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
,
Philosophie
Notizen:
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 ∀m∃n(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 ∀m∃n≦ϕ 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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF00401559
Permalink