Autonomous theory building systems

Theories are collections of large bodies of data in the real world. The authors describe autonomous systems, which observe the outside world and try to generate programs which reproduce the observed data. Methods for generation of new programs are enumeration as well as mutation and combination of old programs. The authors describe two criteria for judging the quality of a program. They can judge a program to be good if it is short and describes a large body of input data. With this criterion the authors show that a system can learn to evaluate arithmetic expressions in polish notation. But they can also judge a program to be good if it allows to compress the total length of descriptions of all observations so far. By the latter criterion a system can create tests which can be used e.g. to partition the programs found so far into directories.