29
$\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$

migrated from cstheory.stackexchange.com Feb 10 '13 at 9:05

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ When comparing two infinite sets, the semantics of "more" have to be revised. $\endgroup$ – Raphael Feb 11 '13 at 5:57
31
$\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$
  • $\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 '13 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 '13 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$ – Roland Pihlakas Aug 17 '18 at 17:41
  • $\begingroup$ @RolandPihlakas that is part of the definition of an algorithm (if you prefer, a computer program). $\endgroup$ – Kaveh Dec 7 '18 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, privacy policy and cookie policy

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