Let C = {(p, q) | either p(0)↓ and q(0)↑ or p(0)↑ and q(0)↓}. Show that C is uncomputable.

Let R = {p | p(0)↓}. R is uncomputable by Rice's theorem.

Let LOOP be a program that loops forever on all inputs.

Define f (p) = (p, LOOP).

Function f is clearly computable. And, for every p

p ∈ R ⇔ p(0)↓
⇔ (p(0)↓ and LOOP(0)↑) or (p(0)↑ and LOOP(0)↓)
⇔ (p, LOOP) ∈ C
⇔ f (p) ∈ C

So f is a mapping reduction from R to C. So R ≤m C.

But relation ≤m is conservative for the computable functions. That is,

If R ≤m C and C is computable then R is computable.

Equivalently,

If R ≤m C and R is uncomputable then C is uncomputable.

But we have shown that R ≤m C and we know that R is uncomputable. Conclude that C is uncomputable.