Computability

PDF of Prof. Santosh’s handwritten notes are here.

Computation

A function f which maps inputs from a domain D to outputs from a range R:

f: D \rightarrow R

If R is finite, we can assume that the output is a single bit \{0, 1\}. (If the output has k bits, we could think of it as k functions, one for each bit).

Example: f(x) = 1 if x is prime.

Computation is the evaluation of functions by a machine with a finite and well-defined set of operations.

Computability

Is every function computable?

To formalize the notion of computability, we will define some terms.

Alphabet \Sigma is a finite set of symbols.

Examples:

\Sigma = \{0,1\}
\Sigma = \{0,1, 2, \dots, 9\}
\Sigma = \{A, B, \dots, Z\}
\Sigma = ASCII

A string is a finite sequence of symbols from the alphabet.

\Sigma^{*} = Set of all strings with elements in \Sigma

A language is a set of strings, i.e., any subset of \Sigma^*

Using the above terminology, we could think of a function as a map from \Sigma^* to \{0,1\}.

The language defined by f, L_f is the set of all input strings which map to 1. Formally, L_f = \{x \in \Sigma^* \vert f(x) = 1\}

Countable Sets

A set S is countable if there exists a map g : S \rightarrow \mathbb{N} such that g is one-to-one and into (injective).

Theorem 1: The set of all strings \Sigma^* over any finite alphabet \Sigma is countable.

Proof:

  • Suppose \Sigma = \{0,1\}.
  • Every string in \Sigma^* is a sequence of 0‘s and 1‘s. We can interpret each string as a number in binary after appending a leading 1. 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 \Sigma is k-ary, we could interpret every string as a number in base k, and thus map every string to the natural number it represents i.e. map string x_1 x_2 \dots x_l to x_l + k x_{l-1} + k^2 x_{l-2} + \dots + k^{l-1} x_1 + k^l.

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 \Sigma^*. Thus, by Theorem 1, the set of all programs is countable.

Theorem 2: The set of all languages over a finite alphabet is uncountable.

Proof:

  • 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 L_1, L_2, \dots where the language L_i corresponds to the language that maps to natural number i. As we proved earlier, the set of all strings is countable, so we can enumerate strings as x_1, x_2, \dots.
  • Consider the language L = \{x_j \vert x_j \notin L_j\}
  • Since we assumed the set of all languages is countable, \exists t \in \mathbb{N} such that L = L_t
  • Does x_t \in L_t? If we assume x_t \in L_t, we have x_t \notin L (=L_t) by the construction of L. If we assume x_t \notin L_t, we have x_t \in L (=L_t). 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.

Advertisements