Jürgen Schmidhuber (December 2020)
Pronounce: You_again Shmidhoobuh AI Blog
@SchmidhuberAI

Genetic Programming for code of unlimited size (1987)

In 2020 we are celebrating the 1/3 century anniversary of our first publications on Genetic Programming or GP for programs of unlimited length (1987) [GP87] [META1] written in a potentially universal programming language [GOD] [GOD34] [CHU] [TUR] [POS]. GP is about solving problems by applying the principles of evolution to programs.

Our paper [GP87] was based on GP for universal programming languages that I had implemented since 1985 on a Symbolics LISP Machine of SIEMENS AG. We partially reimplemented this in the logic programming language PROLOG at my Alma Mater TU Munich. Results were written up with Dirk Dickmanns and Alexander Winklhofer, my fellow students at TUM [GP87] (authors in alphabetical order).

It should be mentioned that Nichael Cramer had an earlier paper on "pure" GP (1985) [GP85]. And even earlier, Stephen F. Smith proposed a related approach as part of a larger system [GP80]. To my knowledge, however, our papers [GP87] [META1] introduced the first "modern" pure GP for automatically evolving programs of unlimited size in a potentially "Turing-complete" coding language [GOD] [GOD34] [CHU] [TUR] [POS].

In the same year, Sec. 2 of my diploma thesis [META1] applied such GP to itself, to recursively evolve better GP methods. There was not only a meta-level but also a meta-meta-level and a meta-meta-meta-level etc. I called this Meta-Evolution. This was the first in a long series of papers on metalearning [META].

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

References

[GP87] D. Dickmanns, J. Schmidhuber, A. Winklhofer (1987): Der genetische Algorithmus: Eine Implementierung in Prolog. Fortgeschrittenenpraktikum, Institut f. Informatik, Lehrstuhl Prof. Radig, Tech. Univ. Munich, 1987. Searchable PDF scan (created by OCRmypdf which uses our LSTM). Source code. [Probably the first work on Genetic Programming for evolving programs of unlimited length written in a potentially universal programming language. Based on work I did since 1985 on a Symbolics Lisp Machine of SIEMENS AG. Authors in alphabetical order. More.]

[GP85] N. Cramer (1985). A Representation for the Adaptive Generation of Simple Sequential Programs. Proc. of an Intl. Conf. on Genetic Algorithms and their Applications, Carnegie-Mellon University, July 24-26, 1985.

[GP80] S. F. Smith (1980). A Learning System Based on Genetic Adaptive Algorithms, PhD Thesis, Univ. Pittsburgh, 1980.

[META1] J. Schmidhuber. Evolutionary principles in self-referential learning, or on learning how to learn: The meta-meta-... hook. Diploma thesis, Institut für Informatik, Technische Universität München, 1987. Searchable PDF scan (created by OCRmypdf which uses LSTM). HTML. [For example, Genetic Programming (GP) is applied to itself, to recursively evolve better GP methods through Meta-Evolution.]

[META] J. Schmidhuber, 2020. Survey: Metalearning Machines Learn to Learn (1987-)

[GOD] K. Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38:173-198, 1931. [In the early 1930s, Gödel founded theoretical computer science. He identified fundamental limits of mathematics and theorem proving and computing and Artificial Intelligence.]

[GOD34] K. Gödel (1934). On undecidable propositions of formal mathematical systems. Notes by S. C. Kleene and J. B. Rosser on lectures at the Institute for Advanced Study, Princeton, New Jersey, 1934, 30 pp. (Reprinted in M. Davis, (ed.), The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Raven Press, Hewlett, New York, 1965.) [Gödel introduced the first universal coding language.]

[CHU] A. Church (1935). An unsolvable problem of elementary number theory. Bulletin of the American Mathematical Society, 41: 332-333. Abstract of a talk given on 19 April 1935, to the American Mathematical Society. Also in American Journal of Mathematics, 58(2), 345-363 (1 Apr 1936). [First explicit proof that the Entscheidungsproblem (decision problem) does not have a general solution.]

[TUR] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, 41:230-267. Received 28 May 1936. Errata appeared in Series 2, 43, pp 544-546 (1937).

[POS] E. L. Post (1936). Finite Combinatory Processes - Formulation 1. Journal of Symbolic Logic. 1: 103-105. Link.
.