Skip to main content Accessibility help
Internet Explorer 11 is being discontinued by Microsoft in August 2021. If you have difficulties viewing the site on Internet Explorer 11 we recommend using a different browser such as Microsoft Edge, Google Chrome, Apple Safari or Mozilla Firefox.

Chapter 2: Generating computable functions

Chapter 2: Generating computable functions

pp. 25-47

Authors

, University of York
  • Add bookmark
  • Cite
  • Share

Summary

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.

    About the book

    Access options

    Review the options below to login to check your access.

    Purchase options

    eTextbook
    US$87.00
    Paperback
    US$87.00

    Have an access code?

    To redeem an access code, please log in with your personal login.

    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.

    Also available to purchase from these educational ebook suppliers