Computability An Introduction to Recursive Function Theory

In this chapter we shall see that various methods of combining computable functions give rise to other computable functions. This will enable us to show quite rapidly that many commonly occurring functions are computable, without writing a program each time – a task that would be rather laborious and tedious.

The basic functions

First we note that some particularly simple functions are computable; from these basic functions (defined in lemma 1.1 below) we shall then build more complicated computable functions using the techniques developed in subsequent sections.

Lemma

The following basic functions are computable:

Proof. These functions correspond to the arithmetic instructions for the URM. Specifically, programs are as follows:

Joining programs together

In each of §§ 3-5 below we need to write programs that incorporate other programs as subprograms or subroutines. In this section we deal with some technical matters so as to make the program writing of later sections as straightforward as possible.

A simple example of program building is when we have programs P and Q, and we wish to write a program for the composite procedure: first do P, and then do Q. Our instinct is to simply write down the instructions in P followed by the instructions in Q. But there are two technical points to consider.

Suppose that P = I1, I2,…, Is. A computation under P is completed when the ‘next instruction for the computation’ is Iv for some v > s; we then require the computation under our composite program to proceed to the first instruction of Q.