Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
When comparing two infinite sets, the semantics of "more" have to be revised. –  Raphael Feb 11 '13 at 5:57
add comment

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.

2 Answers

up vote 15 down vote accepted

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

share|improve this answer
    
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}$ ? –  user1288420 Feb 12 '13 at 12:57
    
It is Cardinal arithmetic. Write the natural numbers in an infinite sequence of natural numbers in binary, that should give the intuition. –  Kaveh Feb 12 '13 at 16:38
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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