35
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ When comparing two infinite sets, the semantics of "more" have to be revised. $\endgroup$
    – Raphael
    Feb 11, 2013 at 5:57

2 Answers 2

37
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ Good answer! What I do not understand (I might be missing something trivial here) is how you get $\mathbb{N}^\mathbb{N} = 2^\mathbb{N}$ ? $\endgroup$
    – hsalin
    Feb 12, 2013 at 12:57
  • $\begingroup$ It is Cardinal arithmetic. Write the natural numbers in an infinite sequence of natural numbers in binary, that should give the intuition. $\endgroup$
    – Kaveh
    Feb 12, 2013 at 16:38
  • $\begingroup$ Why has this assumption to be true - "Each algorithm has a finite description using symbols from a finite set"? Why can't an algorithm have an infinite description? $\endgroup$ Aug 17, 2018 at 17:41
  • 1
    $\begingroup$ @RolandPihlakas that is part of the definition of an algorithm (if you prefer, a computer program). $\endgroup$
    – Kaveh
    Dec 7, 2018 at 5:54
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.