Analysis of combinatory algorithms- A sample of current methodology

Abstract

The study of the computational efficiency and inherent limitations of algorithms for computer solution of problems drawn from classical continuous mathematics has been with us as long as general purpose computers themselves. Similar studies of algorithms of other kinds, however, have been sporadic and isolated until fairly recently. With the growing realization of the critical role played by combinatory algorithms in any instance in which the computer is employed as a logical decision maker, however, has come intensive and widespread interest in understanding such algorithms. Further, these studies have progressed to the point where patterns in analysis have begun to emerge and a summary seems in order. We shall focus our attention here on analytic approaches and methodology, rather than on the specifics of the results obtained. For a summary of the latter, the reader is referred to a companion paper elsewhere in this volume.