On the power of recursive optimizers (Q1114401)

Problems of the effective synthesis of fastest programs (modulo a recursive factor) for recursive functions given by input-output examples or an arbitrary program are investigated. In contrast to the non- existence result proved by \textit{D. A. Alton} and \textit{J. L. Lowther} [Lect. Notes Comput. Sci. 19, 253-265 (1974; Zbl 0311.68035)], and by \textit{D. A. Alton} [J. Comput. Syst. Sci. 12, 368-393 (1976; Zbl 0339.68042)], we show various existence results. Thereby we deal in detail with the influence of the recursive factor in dependence of the concrete formalization of a fastest program. In particular, we shall show that, even for function classes containing arbitrarily complex functions, the effective synthesis of fastest programs (modulo a simple recursive operator) can be achieved sometimes.