We return now to the study of URM-computable functions. Henceforth the term computable standing alone means URM-computable, and program means URM program.
The key fact established in this chapter is that the set of all programs is effectively denumerable1: in other words there is an effective coding of programs by the set of all natural numbers. Among other things, it follows that the class ℘ is denumerable, which implies that there are many functions that are not computable. In § 3 we discuss Cantor's diagonal method, whereby this is established.
The numbering or coding of programs, and particularly its effectiveness, is absolutely fundamental to the development of the theory of computability. We cannot overemphasise its importance. From it we obtain codes or indices for computable functions, and this means that we are able to pursue the idea of effective operations involving such codes.
In § 4 we prove the first of two important theorems involving codes of functions: the so-called s–m–n theorem of Kleene. (The second theorem is the main result of chapter 5.)
Numbering programs
We first explain the terminology that we shall use.
Definitions
(a) A set X is denumerable if there is a bijection f: X → ℕ. (Note. The term countable is normally used to mean finite or denumerable; thus, for infinite sets, countable means the same as denumerable. The term countably infinite is used by some authors instead of denumerable.)
(b) An enumeration of a set X is a surjection g: ℕ → X; this is often represented by writing
X = {x0, x1, x2, …}
where xn = g(n). This is an enumeration without repetitions if g is injective.
(c) Let x be a set of finite objects (for example a set of integers, or a set of instructions, or a set of programs); then X is effectively denumerable if there is a bijection f : X → ℕ such that both f and f-l are effectively computable functions.
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.