2

**Computability**

Some mathematical functions are computable and some are not. In all generalpurpose programming languages, it is possible to write a program for each function that is computable in principle. However, the limits of computability also limit the kinds of things that programming language implementations can do. This chapter contains a brief overview of computability so that we can discuss limitations that involve computability in other chapters of the book.

2.1 **PARTIAL FUNCTIONS AND COMPUTABILITY**

From a mathematical point of view, a program defines a function. The output of a program is computed as a function of the program inputs and the state of the machine before the program starts. In practice, there is a lot more to a program ...

Start Free Trial

No credit card required