The cognitive development of mathematics - Spatial and timing measures associated with algorithms

Abstract

The thesis considers in turn measures of algorithms, measures of programs, and measures of computations. We define an algorithm's measure as the average of the space time requirements of its associated computations, and here, as with measures for programs, a question of optimisation arises: that of finding the algorithm fora function which has the least such measure. The problem of optimisation for algorithmic measure in its general form, proves to be unsolvable, but we show that an effective optimisation procedure does exist with regard to algorithms for finite functions, and give in detail the solution of the special case for functions with a domain of two elements. Further, we reduce the determination of the optimum algorithm for infinite functions to that of calculating the value of a primitive recursive function for any sufficiently large t. Taking a different viewpoint, we investigate the existence of lower bounds to the measures of algorithms for certain functions. A similar analysis is applied to the spatial measure defined for programs, program length, and we discuss some of the philosophical ramifications of program brevity. In addition, a pseudo-spatial measure, the number of instructions a program contains is considered. By using reduction theorems which map onto one another corresponding instructions in equivalent programs, we are able to adapt to this pseudo-spatial measure our results on program length. We then examine a problem of secondary optimisation, which involves a minimisation of both algorithmic and program measure. Measures of computations have been analysed by Myhill, Trakhtenbrot, Smullyan, Ritchie, Cleave, Rabin, Arbib and Blum. An essential element in Blum's definition of computational measure are the 'measuring predicates' and we investigate certain relations between their spatial and timing. Requirements (as where an upper bound on one such quantity places a lower bound on another). The relevant literature is discussed in brief, and we take up a number of points which arise. Most of the arguments and results in the thesis are formulated in terms of Turing machines, but they are applicable to other means of representing algorithms. In the final chapter we investigate how the definition of Turing machines may be extended so as to provide a more authentic model of actual computers both in regard to space-time measure, and to the domain of functions they encompass.