In the previous lesson we gave examples of two noncomputable sets. The set
We also defined computable functions. In this lesson we will use computable functions to create other languages that are not computable. To do so we use the notion of reduction. Informally a reduction takes one decision problem and reduces it to another problems. For example to know your current longitude, you only need to know the time of day in a fixed location. The problem of computing the longitude reduces to the problem of proper time-keeping. This is one way the longitude issue was dealt with before the days of GPS.
Formally we say a language A reduces to language B if there is a computable function f such that for all x in Σ*, x is in A if and only if f(x) is in B.
The power of reductions come from the following lemma.
Lemma: Let A and B be sets such that A is reducible to B.
- If B is computable then A is computable.
- If B is computably enumerable then A is computably enumerable.
- If A is not computable then B is not computable.
- If A is not computably enumerable then B is not computably enumerable.
Lines 1 and 2 are easy to see: Just compute f(x) and simulate the program for B on f(x). Lines 3 and 4 are just the contrapositive of 1 and 2 and turn out to be especially useful.
For example, consider the universal Turing machine language,
Reductions play a major role in computational complexity so it is very instructive to see them in this context. Next lesson we will use more complicated reductions to show other simple languages are not computable.