On the size of sets of computable functions
- 1 October 1973
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 190-196
- https://doi.org/10.1109/swat.1973.23
Abstract
We investigate the size of sets of computable functions using category-theoretic methods (in the sense of the Baire Category theorem). Constructive definitions of no-where dense and meagre set are given and applied to several problems. In particular we apply it to subrecursive degree structures and to a comparison of the power of deterministic and nondeterministic time bounded oracle machines.Keywords
This publication has 3 references indexed in Scilit:
- Decidability of the “almost all” theory of degreesThe Journal of Symbolic Logic, 1972
- A Classification of the Recursive FunctionsMathematical Logic Quarterly, 1972
- Measure and CategoryPublished by Springer Nature ,1971