L(p) is defined to be the set {x | p(x) stops and answers yes}.

Let D = {(p, q) | L(p) ≤m L(q)} Show that D is uncomputable.

It suffices to find an uncomputable set R and to show that R ≤m D.

Let R = {p | L(p) &le_m ∅}.

The only set that can mapping reduct to ∅ is ∅. If A ≠ ∅, then it is clearly not possible for a function f to take a member of A and to produce a member of ∅.

So R = {p | L(p) = ∅}. By Rice's theorem, R is uncomputable.

Let NO be a program that always answer no. That is: 

  NO(x)
    answer no

Of course, L(NO) = ∅.

Define reduction f by f (p) = (p, NO).

It should be clear that f is computable. It should also be clear that, for every p, p ∈ R ⇔ f (p) ∈ D. In case the latter statement is unclear:

p ∈ R ⇔ L(p) = ∅
⇔ L(p) = L(NO)
⇔ (p, NO) ∈ D
⇔ f (p) ∈ D