6.5: Functions and Computability

In Section \(1.3\) we made the off-hand comment that most functions are not defined by rules (by which we meant instructions for computing the function). We consider a rule to be an instruction (in some language) of finite length. Functions that are unambiguously defined by a rule of finite length are called computable, or recursive functions. Naturally there is a complicated mathematical definition of recursive functions, but we shall dispense with the formalities and say that a function is recursive, or computable, if there is an instruction (of finite length) for finding the image of any element in the domain. How many computable functions are there?

We shall restrict our investigation to functions from \(\mathbb{N}\) to \(\mathbb{N}\). We consider functions as graphs of functions. That is, every subset of \(P(\mathbb{N} \times \mathbb{N})\) that satisfies the definition of a function is a function in \(\mathbb{N}^{\mathbb{N}}\). Are all such functions computable? It is obvious that \[2^{\aleph_{0}} \leq\left|\mathbb{N}^{\mathbb{N}}\right| \text {. }\] (Why?) In fact you can show that the sets are bijective. So there are uncountably many functions in \(\mathbb{N}^{\mathbb{N}}\). How many instructions for computing functions are there? An instruction is a finite string, or sequence, of symbols. For instance, an instruction for the function that squares natural numbers is \[f(x)=x^{2} .\] This is a finite sequence of seven symbols. The instruction gives enough information to compute the image of any natural number. There are many other rules for computing this function. For instance the rule \[f(x)=x \cdot x\] obviously defines the same function, but the instruction is different - it contains one more symbol. Consider the set of all possible instructions for computing functions of natural numbers. How are the instructions formulated? One produces a finite sequence of symbols that forms an explicit guide for computing the image of any natural number.

Let \(X\) be the set of all symbols appearing in instructions for computing functions of natural numbers. The set \(X\) will include letters, digits, symbols for operations, symbols for relations and potentially any other symbol that you might see in a book on mathematics. How large is \(X\) ? If you require that every symbol appear in some actual dictionary, it would clearly be finite. You will probably wish to allow any natural number to appear in the instruction. However, although there are infinitely many natural numbers, we need only ten symbols to name them all. It seems that we can reasonably require that \(X\) is finite, but as it turns out, we can allow for \(X\) to be countably infinite without changing our conclusion.

If there is any language with countably many symbols in which the set of all instructions for computing functions could be written, then we may assume that \(X\) is countable. If \(F\) is an instruction or rule (and hence a finite sequence of symbols from \(X\) ), then there is \(N \in \mathbb{N}\) such that \[F \in X^{N} \text {. }\] So it is easily seen that the set of all possible instructions for elements of \(\mathbb{N}^{\mathbb{N}}, I\), satisfies \[I \preceq \bigcup_{N \in \mathbb{N}} X^{N} .\] For \(N \in \mathbb{N}, X^{N}\) is the direct product of \(N\) factors of \(X\), and by Theorem \(6.20\), \[\left|X^{N}\right| \leq \aleph_{0} .\] The set \(\bigcup_{N \in \mathbb{N}} X^{N}\) is the countable union of countable sets, and by Theorem \(6.16\) is countable. Therefore there are uncountably many functions of natural numbers that are not defined by rules.

For a more thorough treatment of set theory, see the book [5] by Yiannis Moschovakis.