Problem Reduction
In the Universal TM / Halting Problem we proved that the "halting problem" is undecidable, translating this into the question of whether a certain language L is undecidable. In a similar way we'll talk about other decision problems, ultimately talking about some underlying language. The essence of "reducing one problem to another" is the existence of a function from one language to another. We want this function to be recursive which means that it must be computable by a TM. A variant on recursive is a partial recursive function, f, for which there is a TM which decides whether f is defined on an input string w
 computes the function value f(w) whenever it is defined
f: Σ^{*} ⇾ Σ^{*}so that, for all w ∈ Σ^{*},
w ∈ L_{1} if and only if f(w) is defined and
f(w) ∈ L_{2}.
Theorem 5.4.1: If L_{1} is not recursive
and there is a
reduction from L_{1} to L_{2}
then L_{2} is not recursive.
The theorem is stated in negative form, because this is how it is used, i.e.,
given one undecidable language (i.e., problem) we reduce it to another
language (i.e., problem) to show that the latter is also undecidable.
The proof is carried out in positive form: argue that if
L_{2} were recursive, then L_{1}
would also be recursive, this being the logical contrapositive of
the theorem statement.
Proof:
The existence of a reduction, f, means there is a Turing Machine pair
(R_{1},R_{2}), which carries out the reduction.
R_{1} decides if f(w) is defined for w and
R_{2} computes f(w).
Suppose that there were a TM M_{2} which could decide L_{2}.
We want to combine (R_{1},R_{2}) and M_{2}
to create the following Turning machine, M_{1},
which would decide L_{1}:
M_{1}:
 Start with: >#w, for w ∈ Σ^{*}. Save w on a spare tape.
 Run R_{1} to decide whether f(w) is defined or not:
R_{1}: >#w ⊢* >#Y (f(w) is defined)
or
R_{1}: >#w ⊢* >#N (f(w) is not defined)  If N is computed in step 2, stop here.

If Y is computed in step 2,
then f(w) is defined, so proceed:

Run R_{2} to compute f(w):
Erase the Y, put w back on the tape and run:
R_{2}: >#w ⊢* >#f(w) 
Run M_{2} from there:
M_{2}: >#f(w) ⊢* >#Y ( f(w) ∈ L_{2} )
or
M_{2}: >#f(w) ⊢* >#N ( f(w) ∉ L_{2} )

Run R_{2} to compute f(w):
Restating the reduction aspect:
w ∈ L_{1}
if and only
if f(w) is defined and
f(w) ∈ L_{2}.
If w ∉ L_{1}
then either f(w) is not defined,
or f(w) is defined and f(w) ∉ L_{2}.
In either case,
M_{1}: >#w ⊢* >#N
If w ∈ L_{1},
then
f(w) is defined and f(w) ∈ L_{2}, in which case:
M_{1}: >#w ⊢* >#Y
Therefore, M_{1} decides L_{1}.
■
Usage of Reduction
The point is to use the Halting problem (i.e., the language HALT) as the "seed" to prove other languages are undecidable. In each case we take a known undecidable language and reduce it to the unknown one, thereby proving that the unknown one is also undecidable.Statement in terms of decision problems
Saying that "problem A reduces to problem B" means that, in some sense, B is equally as general or more general than A, because B can decide for A. The idea of the reduction proofs below is this: Take a general instance of prolem A
 Find a way to transform this general instance into a specific instance of problem B so that "solving B will solve A."
 what exactly is the general instance of problem A
 what exactly is the specific instance of problem B
TM Problem Reductions
Review the basics. For a TM M, L(M) is the language accepted by M, i.e.,L(M) = { x ∈ Σ^{*} : M ↓ x }For the Universal TM, U
L(U) = HALT = { x ∈ {1,c}^{*} : x = E(M,w) and M↓w }
which means that
 If x != E(M,w) for some M and some w, then U runs forever on x.
 If x = E(M,w) and M↓w, then U halts on x.
 If x = E(M,w) and M↑w, then U runs forever on x.
 H_{0}: Given TM M and string w, does M halt on w?
 H_{1}: Given TM M, does M halt on ε?
 H_{2}: Given TM M, does there exist a string w such that M halts on w, i.e., is L(M) = ∅?
 H_{3}: Given TM M, does M halt on all strings w, i.e., is L(M) = Σ^{*}?
 H_{4}: Given TMs M_{1} and M_{2}, do they accept the same languages, i.e., is L(M_{1}) = L(M_{2})?
 H_{5}: Given TM M, is L(M) regular, contextfree, recursive?
 There is a specific TM M_{0} for which the problem is undecidable: given w, does M_{0} halt on w?
Proofs:
 (a): This is the Halting problem with language HALT = { E(M,w): M↓w }

(a) ⇾ (b):
This problem corresponds to the language H_{1} = { E(M): M↓ε } ⊆ {1,c}*.
Instances of H_{1} are simply Turing machines.
From a problem perspective, we want to reduce the Halting problem to this new
problem, which means we must map a (TM,string) pair to a single TM.
The mapping is this:
f( (M,w) ) = M_{w}
where M_{w} is the machine:M_{w}: copy w onto the tape, then behave like M.
Our claim is thatM↓w if and only if M_{w}↓ε
Just think about it about M_{w} running on empty input:[ (s,#) ⊢* (,#w) ] M
From a language perspective, the mapping is f:{1,c}^{*} ⇾ {1,c}^{*}:f( E(M,w) ) = E(M_{w})
We just have to convince ourselves that We can decide, for a string x, whether f(x) is defined, i.e., whether x = E(M,w)

f is computable on a string x = E(M,w), i.e.,
given x = E(M,w) we can
 Extract the separate machine and string parts: M and w
 create the new TM M_{w}
 create its encoding E(M_{w})

(b) ⇾ (c)
(H_{1} ⇾ H_{2}),
and,
(b) ⇾ (d)
(H_{1} ⇾ H_{3})
f( M ) = M′
where M′ is the machine:M′: erase the input from the tape, (i.e. >#w ⊢* >#), then behave like M.
The reduction is from H_{1} to H_{2} (c) or H_{1} to H_{3} (d). M′ simply ignores whatever string is put on the tape by erasing it. Our claim is thatM↓ε if and only if M′↓w, for all w
andM↓ε if and only if M′↓w, for some w

(d) ⇾ (e):
Reduce H_{3} to H_{4}.
Instances of H_{3} are TMs, (M), which halt on all strings.
Instances of H_{4} are TM pairs
(M_{1},M_{2}) which accept the same language.
The transformation is:
f( M ) = (M, A)
where A is the Turing Machine which accepts all strings. ThenM accepts all strings if and only if M and A accept the same set of strings (because A accepts all strings)

(b) ⇾ (f):
Reduce H_{1} to H_{5}.
Instances in both are single TMs.
Instances of H_{1} are TMs which halt on the empty string.
The reduction is this:
f( M ) = M′
Make M′ be a 4tape machine which works like this:
Start with input string x ∈ {1,c}*.
>(#x, >#, >#, >#)
 Copy x to tape 2, then erase tape 1.
(>#, >#x, >#, >#)
 Behave like M on tape 1 (with empty input).
 If M halts, behave like the universal TM, U on tapes 2,3,4.
M↓ε ⇔ L(M′) = HALT (neither regular, contextfree, recursive) M↑ε ⇔ L(M′) = ∅ (regular, contextfree, recursive)
Thus if M′ can decide whether L(M′) is regular, then M′ can decide if L(M′) = ∅, and so
 M′ can decide if M↓ε or not.

Start with input string x ∈ {1,c}*.
 (g): M_{0} is the Universal TM, U. The strings which it cannot decide are E(M,w).