Co-Learnability and FIN-Identifiability of Enumerable Classes of Total Recursive Functions
Abstract
Co-learnability is an inference process where instead of producing the final result, the strategy produces all the natural numbers but one, and the omitted number is an encoding of the correct result. It has been proved in [1] that co-learnability of Goedel numbers is equivalent to EX-identifiability. We consider co-learnability of indices in recursively enumerable (r.e.) numberings. The power of co-learnability depends on the numberings used. Every r.e. class of total recursive functions is co-learnable in some r.e. numbering. FIN-identifiable classes are co-learnable in all r.e. numberings, and classes containing a function being accumulation point are not co-learnable in some r.e. numberings. Hence it was conjectured in [1] that only FIN-identifiable classes are co-learnable in all r.e. numberings. The conjecture is disproved in this paper using a sophisticated construction by V.L. Selivanov.
Cite
Text
Freivalds et al. "Co-Learnability and FIN-Identifiability of Enumerable Classes of Total Recursive Functions." International Conference on Algorithmic Learning Theory, 1994. doi:10.1007/3-540-58520-6_57Markdown
[Freivalds et al. "Co-Learnability and FIN-Identifiability of Enumerable Classes of Total Recursive Functions." International Conference on Algorithmic Learning Theory, 1994.](https://mlanthology.org/alt/1994/freivalds1994alt-colearnability/) doi:10.1007/3-540-58520-6_57BibTeX
@inproceedings{freivalds1994alt-colearnability,
title = {{Co-Learnability and FIN-Identifiability of Enumerable Classes of Total Recursive Functions}},
author = {Freivalds, Rusins and Gobleja, Dace and Karpinski, Marek and Smith, Carl H.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1994},
pages = {100-105},
doi = {10.1007/3-540-58520-6_57},
url = {https://mlanthology.org/alt/1994/freivalds1994alt-colearnability/}
}