Computability An Introduction to Recursive Function Theory

In the real world of computing, the critical question about a function f is not Is f computable?, but rather Is f computable in practical terms? In other words, Is there a program for f that will compute f in the time (or space) we have available? The answer depends partly on our skill in writing programs and the sophistication of our computers; but intuitively we feel that there is an additional factor which can be described as the ‘intrinsic complexity’ of the function f itself. The theory of computational complexity, which we introduce in this chapter, has been developed in order to be able to discuss such questions and to aid the study of the more practical aspects of computability.

Using the URM approach, we can measure the time taken to compute each value of a function f by a particular program, on the assumption that each step of a URM computation is performed in unit time. The time of computation thus defined is an example of a computational complexity measure that reflects the complexity or efficiency of the program being used. (Later we shall mention other complexity measures.)

With a notion of complexity of computation made precise, it is possible to pursue questions such as How intrinsically complex is a computable function f? and Is it possible to find a ‘best’ program for computing f?

The theory of computational complexity is a relatively new field of research; we shall present a small sample of results that have a bearing on the questions raised above. At the end of the chapter we shall provide suggestions for the reader wishing to pursue this topic further.

We begin in § 1 by defining some notation; after some discussion we proceed to show that there are arbitrarily complex computable functions. Section 2 is devoted to the surprising and curious Speed-up theorem of M. Blum, which shows in particular that there are computable functions having no ‘best’ program.