Access Restriction

Author Pager, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1970
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1970-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 17
Issue Number 4
Page Count 7
Starting Page 708
Ending Page 714

Open content in new tab

   Open content in new tab
Source: ACM Digital Library