On the Power of Recursive Optimizers

Author: Thomas Zeugmann

Source: Theoretical Computer Science 62, 1988, 289 - 310.

Abstract. 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 Alton (1974, 1976) 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 arbitrary complex functions, the effective synthesis of fastest programs (modulo a simple recursive operator) can be achieved sometimes.

©Copyright 1988, Elsevier Science Publishers B.V. (North-Holland).
Valid HTML 4.0!