zbMATH — the first resource for mathematics

Inductive inference and computable numberings. (English) Zbl 1221.03035
Summary: It has been previously observed that for many TxtEx-learnable computable families of computably enumerable (c.e. for short) sets all their computable numberings are evidently \(\mathbf 0^{\prime}\)-equivalent, i.e., are equivalent with respect to reductions computable in the halting problem. We show that this holds for all TxtEx-learnable computable families of c.e. sets, and prove that, in general, the converse is not true. In fact, there is a computable family \(\mathcal A\) of c.e. sets such that all computable numberings of \(\mathcal A\) are computably equivalent and \(\mathcal A\) is not TxtEx-learnable. Moreover, we construct a computable family of c.e. sets which is not TxtBC-learnable though all of its computable numberings are \(\mathbf 0^{\prime}\)-equivalent. We also give a natural example of a computable TxtBC-learnable family of c.e. sets which possesses non-\(\mathbf 0^{\prime}\)-equivalent computable numberings. So, for the computable families of c.e. sets, the properties of TxtBC-learnability and \(\mathbf 0^{\prime}\)-equivalence of all computable numberings are independent.

03D25 Recursively (computably) enumerable sets and degrees
68Q32 Computational learning theory
Full Text: DOI
[1] Ambos-Spies, K.; Badaev, S.A.; Goncharov, S.S, On a question of Frank stephan, (), 423-432 · Zbl 1140.03313
[2] Badaev, S.A.; Goncharov, S.S., The theory of numberings: open problems, (), 23-38 · Zbl 0961.03038
[3] Badaev, S.A.; Goncharov, S.S.; Podzorov, S.Yu.; Sorbi, A., Algebraic properties of Rogers semilattices of arithmetical numberings, (), 45-77
[4] Blum, L.; Blum, M., Toward a mathematical theory of inductive inference, Information and control, 28, 125-155, (1975) · Zbl 0375.02028
[5] Ershov, Yu.L., Theory of numberings, (1977), Nauka Moscow · Zbl 0427.03037
[6] Ershov, Yu.L., Theory of numberings, (), 473-503 · Zbl 0948.03040
[7] M. Fulk, 1985. A Study of Inductive Inference Machines. Ph.D. Thesis, SUNY/Buffalo.
[8] Gold, E.M., Language identification in the limit, Information and control, 10, 447-474, (1967) · Zbl 0259.68032
[9] Goncharov, S.S., Autostability of models and abelian groups, Algebra and logic, 19, 1, 13-27, (1980) · Zbl 0468.03022
[10] Goncharov, S.S.; Badaev, S.A., Families with one-element Rogers semilattice, Algebra and logic, 37, 1, 21-34, (1980)
[11] Jain, S.; Sharma, A., Characterizing language identification by standardizing operations, Journal of computer and system sciences, 49, 1, 96-107, (1994) · Zbl 0813.68147
[12] Jain, S.; Sharma, A., Characterizing language identification in terms of computable numberings, Annals of pure and applied logic, 84, 1, 51-72, (1997) · Zbl 0865.03037
[13] Jain, S.; Osherson, D.; Royer, J.S.; Sharma, A., ()
[14] Kummer, M., A learning-theoretic characterization of discrete families of recursive functions, Information processing letters, 54, 205-211, (1995) · Zbl 0875.68271
[15] Mal’cev, A.I., Positive and negative numberings, Soviet math. dokl., 160, 75-77, (1965)
[16] Odifreddi, P.G., Classical recursion theory. vol. II, () · Zbl 0931.03057
[17] G. Schäfer-Richter, 1984. Über Eingabeabhängigkeit und Komplexität von Inferenzstrategien. Ph.D. Thesis, RWTH Aachen.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.