Report Number: CS-TR-72-253
Institution: Stanford University, Department of Computer Science
Title: Total complexity and the inference of best programs.
Author: Feldman, Jerome A.
Author: Shields, Paul C.
Date: April 1972
Abstract: Axioms for a total complexity measure for abstract programs are presented. Essentially, they require that total complexity be an unbounded increasing function of the Blum time and size measures. Algorithms for finding the best program on a finite domain are presented, and their limiting behaviour for infinite domains described. For total complexity, there are important senses in which a machine $underline{can}$ find the best program for a large class of functions.