Back to Search
Start Over
Inductive inference and computable numberings
- Source :
-
Theoretical Computer Science . Apr2011, Vol. 412 Issue 18, p1652-1668. 17p. - Publication Year :
- 2011
-
Abstract
- Abstract: It has been previously observed that for many -learnable computable families of computably enumerable (c.e. for short) sets all their computable numberings are evidently -equivalent, i.e. are equivalent with respect to reductions computable in the halting problem. We show that this holds for all -learnable computable families of c.e. sets, and prove that, in general, the converse is not true. In fact there is a computable family of c.e. sets such that all computable numberings of are computably equivalent and is not -learnable. Moreover, we construct a computable family of c.e. sets which is not -learnable though all of its computable numberings are -equivalent. We also give a natural example of a computable -learnable family of c.e. sets which possesses non--equivalent computable numberings. So, for the computable families of c.e. sets, the properties of -learnability and -equivalence of all computable numberings are independent. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 412
- Issue :
- 18
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 59186862
- Full Text :
- https://doi.org/10.1016/j.tcs.2010.12.041