Computability Theory

The Computability Concept 27

Very much the same situation occurs with computability. It is fair to ask whether

the precise concept of a computable partial function is an accurate formalization of the

informal concept of an effectively calculable function. Again, the precisely defined

class appears to be, if anything, too broad, because it includes functions requiring,

for large inputs, absurd amounts of computing time. Computability corresponds to

effective calculability in an idealized world, where length of computation and amount

of memory space are disregarded. But in any event, the class of computable partial

functions has been found to be a natural ...