On learning limiting programs

ABSTRACT

Machine learning of limit programs (i.e., programs allowed finitely many mind changes about their legitimate outputs) for computable functions is studied. Learning of iterated limit programs is also studied. To partially motivate these studies, it is shown that, in some cases, interesting global properties of computable functions can be proved from suitable (n+1)-iterated limit programs for them which can not be proved from any n-iterated limit programs for them. It is shown that learning power is increased when (n+1)-iterated limit programs rather than n-iterated limit programs are to be learned. Many tradeoff results are obtained regarding learning power, number (possibly zero) of limits taken, program size constraints, and number of errors tolerated in final programs learned.

REFERENCES

• AS83: Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983 [doi>10.1145/356914.356918]
• Bar74: J.M. Barzdin. Two theorems on the limiting synthesis of functions. In Theory of Algorithms and Programs, Latvian State University, Riga, 210:82-88, 1974. In Russian.
• BB75: L. Blum and M. Blum. Toward a mathematical theory of inductive inference. Information and Control, 28:125-155, 1975.
• BCJS92: Ganesh Baliga , John Case , Sanjay Jain , Mandayam Suraj, Machine Learning of Higher Order Programs, Proceedings of the Second International Symposium on Logical Foundations of Computer Science, p.9-20, July 20-24, 1992
• Blu67: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• Cas74: J. Case. Periodicity in generations of automata. Mathematical Systems Theory, 8:15- 32, 1974.
• Cas86: J. Case. Learning machines. In W. Demopoulos and A. Marras, editors, Language Learning and Concept Acquisition. Ablex Publishing Company, 1986.
• CCJ92: John Case , Keh-Jiann Chen , Sanjay Jain, Strong separation of learning classes, Journal of Experimental & Theoretical Artificial Intelligence, v.4 n.4, p.281-293, Oct.–Dec. 1992 [doi>10.1080/09528139208953752]
• Che81: Keh-Jiann Chen, Tradeoffs in machine inductive inference, 1981
• Che82: K. Chen. Tradeoffs in inductive inference of nearly minimal sized programs. Information and Control, 52:68-86, 1982.
• CJS90: J. Case, S. Jain, and A. Sharma. Anomalous learning helps succinctness. In S. Arikawa, S. Goto, S. Ogsuga, and T. Yokomori, editors, Proceedings of the First Workshop on Algorithmic Learning Theory, Tokyo, Japan, pages 282-288. Japanese Society for Artificial Intelligence, October 1990.
• Cra53: W. Craig. On axiomatizability within a system. Journal of Symbolic Logic, 18:30-32, 1953.
• CS83: J. Case and C. Smith. Comparison of identification criteria for machine inductive inference. Theoretical Computer Science, 25:193- 220, 1983.
• Fef60: S. Feferman. Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae, 49:35-92, 1960.
• Fre75: R. Freivalds. Minimal GSdel numbers and their identification in the limit. Lecture Notes in Computer Science, 32:219-225, 1975.
• Ful85: Mark Andrew Fulk, A study of inductive inference machines, State University of New York at Buffalo, Buffalo, NY, 1986
• Gol65: E.M. Gold. Limiting recursion. Journal of Symbolic Logic, 30:28-48, 1965.
• Gol67: E.M. Gold. Language identification in the limit. Information and Control, 10:447-474, 1967.
• HU79: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• KW80: R. Klette and R. Wiehagen. Research in the theory of inductive inference by GDR mathematicians - A survey. Information Sciences, 22:149-169, 1980.
• LMF76: N. Lynch, A. Meyer, and M. Fischer. Relativization of the theory of computational complexity. Transactions of the American Mathematical Society, 220:243-287, 1976.
• Mar89: Y. Marcoux. Composition is almost as good as s-1-1. In Proceedings, Structure in Complexity Theory-Fourth Annual Conference. IEEE Computer Society Press, 1989.
• Men86: Elliott Mendelson, Introduction to mathematical logic (3rd ed.), Wadsworth Publ. Co., Belmont, CA, 1987
• MY78: Michael Machtey , Paul Young, An Introduction to the General Theory of Algorithms, Elsevier Science Inc., New York, NY, 1978
• OSW86: Daniel N. Osherson , Michael Stob , Scott Weinstein, Systems that learn: an introduction to learning theory for cognitive and computer scientists, MIT Press, Cambridge, MA, 1986
• Put65: H. Putnam. Trial and error predicates and the solution to a problem of Mostowski. Journal of Symbolic Logic, 30:49-57, 1965.
• RC92: J. Royer and J. Case. Intensional Subrecursion and Complexity Theory. Research Notes in Theoretical Science. Pitman Press, being revised for expected publication, 1992.
• Ric80: Gregory Anthony Riccardi, The independence of control structures in abstract programming systems, 1980
• Ric81: G. Riccardi. The independence of control structures in abstract programming systems. Journal of Computer and System Sciences, 22:107-143, 1981.
• Rog58: H. Rogers. GSdel numberings of partial recursive functions. Journal of Symbolic Logic, 23:331-341, 1958.
• Rog67: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• Roy87: James S. Royer, A connotational theory of program structure, Springer-Verlag New York, Inc., New York, NY, 1987
• Sha71: N. Shapiro. Review of "Limiting recursion" by E.M. Gold and "Trial and error predicates and the solution to a problem of Mostowski" by H. Putnam. Journal of Symbolic Logic, 36:342, 1971.
• Sho59: J. Shoenfield. On degrees of unsolvability. Annals of Mathematics, 69:644-653, 1959.
• Sho71: J. Shoenfield. Degrees of Unsolvability. North-Holland, 1971.
• Soa87: Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag New York, Inc., New York, NY, 1987
• Wie78: R. Wiehagen. Zur Therie der Algrithmischen Erkennung. PhD thesis, Humboldt- Universitat, Berlin, 1978.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.0 General

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Theory, Verification