Computable function

1.1 Models of computation
Some mathematical functions are computable and some are not: There are problems for which no computer program can provide a solution even assuming that the amount of time and space available to carry out the computation is infinite. Complexity theory studies the “practical” aspects of computability; that is, for a computable function, it answers the question: How much time and space will be needed for the computation? We will not cover complexity theory in this book but instead will concentrate on computability.

First we need to define precisely the notion of a computable function. This is a difficult task and is still the subject of research. We will first give an intuitive definition.

Definition 1.2 (Computable function)
All the functions on the natural numbers that can be effectively computed in an ideal world, where time and space are unlimited, are called partial recursive functions or computable functions.

The definition of a computable function above does not say what our notion of “effective” computation is: Which programming language is used to define the function? What kind of device is used to compute it? We need a model of computation to abstract away from the material details of the programming language and the processor we are using. In fact, computability was studied as a branch of mathematical logic well before programming languages and computers were built. Three well-studied abstract models of computation dating from the 1930s are

• Turing machines, designed by Alan Turing to provide a formalisation of the concept of an algorithm;

• the Lambda calculus, designed by Alonzo Church with the aim of providing a foundation for mathematics based on the notion of a function; and

• the theory of recursive functions, first outlined by Kurt G¨odel and further developed by Stephen Kleene.

These three models of computation are equivalent in that they can all express the same class of functions. Indeed, Church’s Thesis says that they compute all the so-called computable functions. More generally, Church’s Thesis says that the same class of functions on the integers can be computed in any sequential, universal model of computation that satisfies basic postulates about determinism and the effectiveness of elementary computation steps. This class of computable functions is the set of partial recursive functions.

We say that a programming language is Turing complete if any computable function can be written in this language. All general-purpose programming languages available nowadays are complete in this sense. Turing completeness is usually proved through an encoding in the programming language of a standard universal computation model.