On the Efficiency of Algorithms

Publisher Website
Google Scholar
Abstract
A definition is given of the efficiency of an algorithm considered as a whole. This immediately raises the question of whether it is possible to find the most efficient or “optimum” algorithm. It is shown that an optimization problem of this kind is effectively solvable if and only if the set of arguments with which one is concerned is a finite one. Next, conditions under which an optimum algorithm does or does not exist are considered, and a limiting recursive process for finding it when it does is produced. Finally, some observations are made about the best space-time measure for algorithms which can be expected in certain cases. The results and proofs are couched in terms of Turing machines but may be adapted without difficulty to apply to other infinite digital machines such as the extensions of actual computers obtained by adding an infinite memory, or to the computations involved in other theoretical formulations of partial recursive functions such as those provided by Kleene's systems of equations or the URM's of Shepherdson and Sturgis.

This publication has 8 references indexed in Scilit: