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:
(a) the zero function O(O(x) = 0 for all x);
(b) the successor function x + 1
(c) for each n ≥ 1 and 1 ≤ i ≤ n, the projection function given by
Proof. These functions correspond to the arithmetic instructions for the URM. Specifically, programs are as follows:
(a) 0: program Z(l);
(b) x + l: program S(l);
(c) program T(i, 1).
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.
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.