In the previous lesson we gave examples of two noncomputable sets. The set

_{A}= { <M> | Machine M does accept input <M>}

_{D}= { <M> | Machine M does not accept input <M>}

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,

_{U}= { (<M>,x) | Machine M does accept input x}

_{U}is computably enumerable. Let f(<M>)=(<M>,<M>). The function f is easily seen to be computable and reduces L

_{A}to L

_{U}. Thus by our Lemma, line 3, we have that L

_{U}is not computable.

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.

## No comments:

## Post a Comment