Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-06T04:24:47.816Z Has data issue: false hasContentIssue false
  • English
  • Français

Machine learning of higher-order programs

Published online by Cambridge University Press:  12 March 2014

Ganesh Baliga ,
John Case ,
Sanjay Jain  and
Mandayam Suraj
Ganesh Baliga
Affiliation:
Department of Computer and Information Sciences, University of Delaware, Newark, Delaware 19176, E-mail: [email protected]
John Case
Affiliation:
Department of Computer and Information Sciences, University of Delaware, Newark, Delaware 19176, E-mail: [email protected]
Sanjay Jain
Affiliation:
Institute of Systems Science, National University of Singapore, Singapore0511, E-mail: [email protected]
Mandayam Suraj
Affiliation:
Department of Computer and Information Sciences, University of Delaware, Newark, Delaware 19176, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A generator program for a computable function (by definition) generates an infinite sequence of programs all but finitely many of which compute that function. Machine learning of generator programs for computable functions is studied. To motivate these studies partially, it is shown that, in some cases, interesting global properties for computable functions can be proved from suitable generator programs which cannot be proved from any ordinary programs for them. The power (for variants of various learning criteria from the literature) of learning generator programs is compared with the power of learning ordinary programs. The learning power in these cases is also compared to that of learning limiting programs, i.e., programs allowed finitely many mind changes about their correct outputs.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 2 , June 1994 , pp. 486 - 500
Copyright
Copyright © Association for Symbolic Logic 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[AS83] Angluin, D. and Smith, C., A survey of inductive inference: Theory and models, Computing Surveys, vol. 15 (1983), pp. 237–289.Google Scholar
[Bar74] Barzdin, J. M., Two theorems on the limiting synthesis of functions, Theory of algorithms and programs, Latvian State University, Riga, vol. 210 (1974), pp. 82–88, (Russian)Google Scholar
[BB75] Blum, L. and Blum, M., Toward a mathematical theory of inductive inference, Information and Control, vol. 28 (1975), pp. 125–155.Google Scholar
[Blu67] Blum, M., A machine independent theory of the complexity of recursive functions, Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336.Google Scholar
[Cas74] Case, J., Periodicity in generations of automata, Mathematical Systems Theory, vol. 8 (1974), pp. 15–32.Google Scholar
[Cas86] Case, J., Learning machines, Language learning and concept acquistion (Demopoulos, W. and Marras, A., editors), Ablex Publishing Company, 1986.Google Scholar
[Che81] Chen, K., Tradeoffs in machine inductive inference, Ph.D. Thesis, State University of New York at Buffalo, Buffalo, New York, 1981.Google Scholar
[CJS92] Case, J., Jain, S., and Sharma, A., On learning limiting programs, International Journal of Foundations of Computer Science, vol. 3 (1992), pp. 93–115.CrossRefGoogle Scholar
[CL82] Case, J. and Lynes, C., Proceedings of the 9th international colloquium on automata, languages, and programming (Nielson, M. and Schmidt, E. M., editors), vol. 140, Springer-Verlag, Berlin, 1982, pp. 107–115.Google Scholar
[Cra53] Craig, W., On axiomatizability within a system, this Journal, vol. 18 (1953), pp. 30–32.Google Scholar
[CS83] Case, J. and Smith, C., Comparison of identification criteria for machine inductive inference, Theoretical Computer Science, vol. 25 (1983), pp. 193–220.Google Scholar
[Feff60] Feferman, S., Arithmetization of metamathematics in a general setting, Fundamenta Mathematicae, vol. 49 (1960), pp. 35–92.Google Scholar
[Fis65] Fischer, P., Theory of provable recursive functions, Transactions of the American Mathematical Society, vol. 117 (1965), pp. 494–520.CrossRefGoogle Scholar
[Ful85] Fulk, M., A study of inductive inference machines, Ph.D. Thesis, State University of New York at Buffalo, Buffalo, New York, 1985.Google Scholar
[Gol65] Gold, E. M., Limiting recursion, this Journal, vol. 30 (1965), pp. 28–48.Google Scholar
[Gol67] Gold, E. M., Language identification in the limit, Information and Control, vol. 10 (1967), pp. 447–474.Google Scholar
[HU79] Hopcroft, J. and Ullman, J., Introduction to automata theory languages and computation, Addison-Wesley Publishing Company, Reading, Massachusetts, 1979.Google Scholar
[Kre51] Kreisel, G., On the interpretation of nonfinitist proofs, this Journal, vol. 17 (1951), pp. 241–267.Google Scholar
[Kre58] Kreisel, G., Mathematical significance of consistency proofs, this Journal, vol. 23 (1958), pp. 155–182.Google Scholar
[KW80] Klette, R. and Wiehagen, R., Research in the theory of inductive inference by GDR mathematicians—A survey, Information Sciences, vol. 22 (1980), pp. 149–169.Google Scholar
[LMF76] Lynch, N., Meyer, A., and Fischer, M., Relativization of the theory of computational complexity, Transactions of the American Mathematical Society, vol. 220 (1976>, pp. 243–287.Google Scholar
[Men86] Mendelson, E., Introduction to mathematical logic, 3rd edition, Brooks-Cole, San Francisco, 1986.Google Scholar
[MY78] Machtey, M. and Young, P., An introduction to the general theory of algorithms, North-Holland, New York, 1978.Google Scholar
[OSW86] Osherson, D., Stob, M., and Weinstein, S., Systems that learn, an introduction to learning theory for cognitive and computer scientists, MIT Press, Cambridge, Massachusetts, 1986.Google Scholar
[Put65] Putnam, H., Trial and error predicates and the solution to a problem of Mostowski, this Journal, vol. 30 (1965), pp. 49–57.Google Scholar
[RC92] Royer, J. and Case, J., Intensional subrecursion and complexity theory, Research Notes in Theoretical Science, Pitmann Press, being revised for expected publication, 1992.Google Scholar
[Rog57] Rogers, H., Provably recursive functions, Bulletin of the American Mathematical Society, vol. 63 (1957), p. 140.Google Scholar
[Rog58] Rogers, H., Gödel numberings of partial recursive functions, this Journal, vol. 23 (1958>, pp. 331–341.,+pp.+331–341.>Google Scholar
[Rog67] Rogers, H., Theory of recursive functions and effective computability, McGraw Hill, New York, 1967: reprinted, MIT Press, Cambridge, Massachusetts. 1987.Google Scholar
[Ros84] Rose, H., Subrecursion: functions and hierarchies, Oxford University Press, London and New York, 1984.Google Scholar
[Sha71] Shapiro, N., Review of “Limiting recursion” by E. M. Gold and “Trial and error predicates and the solution to a problem of Mostowski” by H. Putnam, this Journal, vol. 36 (1971), p. 342.Google Scholar
[Sho59] Shoenfield, J., On degrees of unsolvability, Annals of Mathematics (2), vol. 69 (1959), pp. 644–653.Google Scholar
[Sho71] Shoenfield, J., Degrees of unsolvability, North-Holland, Amsterdam, 1971.Google Scholar
[Soa87] Soare, R., Recursively enumerable sets and degrees, Springer-Verlag, Berlin and New York, 1987.Google Scholar
[Wie78] Wiehagen, R., Zur Theorie der Algorithmischen Erkennung, Ph.D. Thesis, Hunboldt-Universitat, Berlin, 1978.Google Scholar