Inductive Inference of Optimal Programs: A Survey and Open Problems

Author: Thomas Zeugmann

Source: “Nonmonotonic and Inductive Logic, 1st International Workshop, Karlsruhe, Germany, December 1990, Proceedings,” (J. Dix, K.P. Jantke, and P.H. Schmitt, Eds.), Lecture Notes in Artificial Intelligence 543, pp. 208-222, Springer-Verlag 1991.

Abstract. The present paper surveys results and presents open problems concerning the llmitlng-effective synthesis of opti- mal programs for recurslve functions given by input-output examples.
Five different formalizations of the intuitive notion “optimal program” are given. In particular, it is studied under what conditions the knowledge that every function from a function class does possess an “optimal program” is sufficient to infer such an “optimal program” in the limit for each function contained in the class.