Case, John; Kaufmann, Susanne; Kinber, Efim; Kummer, Martin Learning recursive functions from approximations. (English) Zbl 0880.68107 J. Comput. Syst. Sci. 55, No. 1, 183-196 (1997). Summary: This article investigates algorithmic learning, in the limit, of correct programs for recursive functions \(f\) from both input/output examples of \(f\) and several interesting varieties of approximate additional (algorithmic) information about \(f\). Specifically considered, as such approximate additional information about \(f\), are Rose’s frequency computations for \(f\) and several natural generalizations from the literature, each generalization involving programs for restricted trees of recursive functions which have \(f\) as a branch. Considered as the types of trees are those with bounded variation, bounded width, and bounded rank. For the case of learning final correct programs for recursive functions, EX-learning, where the additional information involves frequency computations, an insightful and interestingly complex combinatorial characterization of learning power is presented as a function of the frequency parameters. For EX-learning (as well as for BC-learning, where a final sequence of correct programs is learned), for the cases of providing the types of additional information considered in this paper, the maximal probability is determined such that the entire class of recursive functions is learnable with that probability. Cited in 7 Documents MSC: 68T05 Learning and adaptive systems in artificial intelligence Keywords:algorithmic learning; frequency computations × Cite Format Result Cite Review PDF Full Text: DOI References: [1] Amir, A.; Gasarch, W. I., Polynomial terse sets, Inform. and Comput., 77, 37-56 (1988) · Zbl 0646.68049 [2] Angluin, D.; Gasarch, W. I.; Smith, C. H., Training sequences, Theoret. Comput. Sci., 66, 255-272 (1989) · Zbl 0734.68080 [3] Baliga, G.; Case, J., Learning with higher order additional information, Proceedings 4th AII’94. Proceedings 4th AII’94, Lecture Notes in Computer Science, 872 (1994), Springer-Verlag: Springer-Verlag Berlin, p. 64-75 · Zbl 1044.68637 [4] Beigel, R.; Gasarch, W. I.; Gill, J.; Owings, J. C., Terse, superterse, and verbose sets, Inform. and Comput., 103, 68-85 (1993) · Zbl 0781.68057 [5] Beigel, R.; Kummer, M.; Stephan, F., Quantifying the amount of verboseness, Inform. and Comput., 118, 73-90 (1995) · Zbl 0827.68082 [6] Beigel, R.; Kummer, M.; Stephan, F., Approximable sets, Inform. and Comput., 120, 304-314 (1995) · Zbl 0835.68043 [7] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. K., Learnability and the Vapnik-Chervonenkis dimension, Assoc. Comput. Mach., 36, 929-965 (1989) · Zbl 0697.68079 [8] Brooks, R.; Mataric, M., Real robots, real learning problems, Robot Learning (1993), Kluwer Academic: Kluwer Academic Boston, p. 193-234 [9] Case, J.; Smith, C. H., Identification criteria for machine inductive inference, Theoret. Comput. Sci., 25, 193-220 (1983) · Zbl 0524.03025 [10] Chaitin, G. J., Program size, oracles, and the jump operation, Osaka J. Math., 14, 139-149 (1977) · Zbl 0359.94031 [11] Chang, K., A purely geometric module in the rat’s spatial representation, Cognition, 23, 149-178 (1986) [13] Degtev, A. N., On \((mn\), (Moldavanskij, D. I., Algebraic Systems (1981), Ivanova Gos. Univ. Press), 88-99 · Zbl 0513.00006 [14] Fortnow, L.; Gasarch, W. I.; Jain, S.; Kinber, E.; Kummer, M.; Kurtz, S.; Pleszkoch, M.; Slaman, T.; Solovay, R.; Stephan, F., Extremes in the degrees of inferability, Ann. Pure Appl. Logic, 66, 231-276 (1994) · Zbl 0813.03026 [15] Freivalds, R. V., Inductive inference of recursive functions: Qualitative theory, Baltic Computer Science. Baltic Computer Science, Lecture Notes in Computer Science, 502 (1991), Springer-Verlag: Springer-Verlag Berlin, p. 77-110 · Zbl 1415.03045 [16] Freivalds, R. V.; Wiehagen, R., Inductive inference with additional information, EIK, 15, 179-185 (1979) · Zbl 0437.03018 [17] Gallistel, C., The Organization of Learning (1990), MIT Press: MIT Press Cambridge [18] Gasarch, W. I.; Smith, C. H., Learning via queries, Assoc. Comput. Mach., 39, 649-674 (1992) · Zbl 0799.68155 [19] Harizanov, V.; Kummer, M.; Owings, J. C., Frequency computation and the cardinality theorem, J. Symbolic Logic, 57, 677-681 (1992) [21] Kaufmann, S.; Kummer, M., On a quantitative notion of uniformity, Fundamenta Inform., 25, 59-78 (1996) · Zbl 0840.68043 [22] Kinber, E., On frequency calculations of general recursive predicates, Sov. Math. Dokl., 13, 873-876 (1972) · Zbl 0264.02039 [23] Kinber, E., Candidate dissertation (1975) [24] Kuipers, B., Modeling spatial knowledge, Cognitive Sci., 2, 129-153 (1978) [26] Kummer, M., A proof of Beigel’s cardinality conjecture, J. Symbolic Logic, 57, 682-687 (1992) · Zbl 0763.03025 [28] Kummer, M.; Stephan, F., The power of frequency computation, Proceedings FCT’95. Proceedings FCT’95, Lecture Notes in Computer Science (1995), Springer-Verlag: Springer-Verlag Berlin · Zbl 1508.68114 [30] Li, M.; Vitányi, P., An Introduction to Kolmogorov Complexity and Its Applications (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0805.68063 [31] Loveland, D. W., A variant of the Kolmogorov concept of complexity, Inform. and Control, 15, 510-526 (1969) · Zbl 0188.52101 [32] Margules, J.; Gallistel, C., Heading in the rat: Determination by environmental shape, Animal Learning and Behav., 16, 404-410 (1988) [33] Mataric, M., Integration of representation into goal-driven behavior-based robots, IEEE Trans. Robotics and Automation, 8, 304-312 (1992) [34] McDermott, D., Robot planning, AI Magazine, 13, 55-79 (1992) [35] Odifreddi, P., Classical Recursion Theory (1989), North-Holland: North-Holland Amsterdam · Zbl 0931.03057 [36] Osherson, D.; Stob, M.; Weinstein, S., Systems that Learn (1986), MIT Press: MIT Press Cambridge [37] Owings, J. C., A cardinality version of Beigel’s nonspeedup theorem, J. Symbolic Logic, 54, 761-767 (1989) · Zbl 0685.03034 [38] Pitt, L., Probabilistic inductive inference, J. Assoc. Comput. Machin., 36, 383-433 (1989) · Zbl 0676.68046 [40] Smith, C. H., The power of pluralism for automatic program synthesis, J. Assoc. Comput. Machin., 29, 1144-1165 (1982) · Zbl 0496.68065 [41] Soare, R. I., Recursively Enumerable Sets and Degrees (1987), Springer-Verlag: Springer-Verlag Berlin · Zbl 0667.03030 [42] Trakhtenbrot, B. A., On frequency computation of functions, Algebra i Logika, 2, 25-32 (1963) · Zbl 0192.05001 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.