Why are there more non-computable functions than computable ones?

Question

I'm currently reading a book in algorithms and complexity. At the moment I'm, reading about computable and non-computable functions, and my book states that there are many more functions that are non-computable than computable, in fact the majority is non-computable it says. In some sense I can intuitively accept that but the book does not give a formal proof nor does it elaborate much on the topic.

I just wanted to see a proof/let someone here elaborate about it/understand more strictly why there are so many more non-computable functions than computable ones.

Answer 1

The are countably many computable functions:

Each computable function has at least one algorithm. Each algorithm has a finite description using symbols from a finite set, e.g. finite binary strings using symbols $\{0,1\}$. The number of finite binary strings denoted by $\{0,1\}^*$ is countable (i.e. the same as the number of natural numbers $\mathsf{N}$).

Therefore there can be at most countably many computable functions. There are at least countable many computable function since for each $c\in \{0,1\}^*$, the constant function $f(x)=c$ is computable.

In other words, there is a correspondence between:

• the set of computable functions,
• the set of algorithms,
• $\{0,1\}^*$, the set of finite strings from $\{0,1\}$, and
• $\mathbb{N}$, the set of natural numbers.

On the other hand, there are uncountably many functions over strings (or natural numbers). A function $f:\mathbb{N} \to \mathbb{N}$ (or $f:\{0,1\}^* \to \{0,1\}^*$) assigns a value for each input. Each of these values can be chosen independently from others. So there are $\mathbb{N}^\mathbb{N}=2^\mathbb{N}$ possible function. The number of functions over natural numbers is equal to the number of real numbers.

Since only countably many of functions are computable, most of them are not. In fact the number of uncomputable functions is also $2^{\mathbb{N}}$.

If you want to picture this intuitively, think about natural numbers and real numbers, or about finite binary strings and infinite binary strings. There are way more real numbers and infinite binary strings than natural numbers and finite strings. In other words $\mathbb{N} < 2^\mathbb{N}$ (for a proof of this fact see Cantor's diagonal argument and Cardinal arithmetic).

Answer 2

Here is an "explicit" construction of uncountably many non-computable Boolean functions. Let $K$ be some fixed non-computable Boolean function, say the characteristic function of the halting problem. Consider the set of functions $$ F = \{ f \colon \mathbb{N} \to \{0,1\} : \forall x \in \mathbb{N}, f(2x) = K(x) \}. $$ Each $f \in F$ is non-computable, and $F$ is uncountable.

There is a similar construction with computable functions. Given a computable function $R$, let $$ G = \{ g \colon \mathbb{N} \to \{0,1\} : \exists n \in \mathbb{N} \forall m \geq n, g(m) = R(m). \} $$ In other words, $g \in G$ if it differs from $R$ on finitely many values. All functions in $G$ are computable (hard-code the finitely many differences). In contrast to the previous situation, $G$ is countable.

So there are lots of non-computable function since we have "infinitely many" degrees of freedom - actual infinity rather than "potential" infinity like in the computable case.