A function which maps inputs from a domain to outputs from a range :
If is finite, we can assume that the output is a single bit . (If the output has k bits, we could think of it as functions, one for each bit).
Example: if is prime.
Computation is the evaluation of functions by a machine with a finite and well-defined set of operations.
Is every function computable?
To formalize the notion of computability, we will define some terms.
Alphabet is a finite set of symbols.
A string is a finite sequence of symbols from the alphabet.
Set of all strings with elements in
A language is a set of strings, i.e., any subset of
Using the above terminology, we could think of a function as a map from to .
The language defined by , is the set of all input strings which map to . Formally,
A set is countable if there exists a map such that is one-to-one and into (injective).
Theorem 1: The set of all strings over any finite alphabet is countable.
- Suppose .
- Every string in is a sequence of ‘s and ‘s. We can interpret each string as a number in binary after appending a leading . Thus, we could map each string to the natural number it represents. It is easy to see that this map is one-one and into.
- For the general case, when is k-ary, we could interpret every string as a number in base , and thus map every string to the natural number it represents i.e. map string to .
Programs are sets of instructions for machines, represented as strings over some finite alphabet. Not every string represents a program but all programs can be represented as strings. This means that the set of all programs is a subset of . Thus, by Theorem 1, the set of all programs is countable.
Theorem 2: The set of all languages over a finite alphabet is uncountable.
- Assume that the set of all languages is countable. This means that there exists a one-to-one and into function which maps every language to a natural number. Since such a map exists, we can enumerate languages as where the language corresponds to the language that maps to natural number . As we proved earlier, the set of all strings is countable, so we can enumerate strings as .
- Consider the language
- Since we assumed the set of all languages is countable, such that
- Does ? If we assume , we have by the construction of . If we assume , we have . Thus, we have a contradiction in either case. This proves that the set of all languages is uncountable.
Since the set of all programs is countable while the set of all languages is uncountable, there exist (infinitely many) languages which have no programs to decide them.