Total Complexity and the Inference of Best Programs
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 can find the best program for a large class of functions.
- Theoretical Mathematics
- Computer Programming and Software