## TM Undecidable Problems

### 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

Definition 5.4.1: Given two languages L1, L2 ⊆ Σ*. A reduction from L1 to L2 is a partial recursive function
```f: Σ* ⇾ Σ*
```
so that, for all w ∈ Σ*,
w ∈ L1 if and only if f(w) is defined and f(w) ∈ L2.
Theorem 5.4.1: If L1 is not recursive and there is a reduction from L1 to L2 then L2 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 L2 were recursive, then L1 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 (R1,R2), which carries out the reduction. R1 decides if f(w) is defined for w and R2 computes f(w).

Suppose that there were a TM M2 which could decide L2. We want to combine (R1,R2) and M2 to create the following Turning machine, M1, which would decide L1:

M1:
1. Start with: >#w, for w ∈ Σ*. Save w on a spare tape.
2. Run R1 to decide whether f(w) is defined or not:
R1: >#w ⊢* >#Y   (f(w) is defined)
or
R1: >#w ⊢* >#N   (f(w) is not defined)
3. If N is computed in step 2, stop here.
4. If Y is computed in step 2, then f(w) is defined, so proceed:
1. Run R2 to compute f(w):
Erase the Y, put w back on the tape and run:
R2: >#w ⊢* >#f(w)
2. Run M2 from there:
M2: >#f(w) ⊢* >#Y   ( f(w) ∈ L2 )
or
M2: >#f(w) ⊢* >#N   ( f(w) ∉ L2 )

Restating the reduction aspect:
w ∈ L1   if and only   if f(w) is defined and f(w) ∈ L2.
If w ∉ L1 then either f(w) is not defined, or f(w) is defined and f(w) ∉ L2. In either case,
M1: >#w ⊢* >#N
If w ∈ L1, then f(w) is defined and f(w) ∈ L2, in which case:
M1: >#w ⊢* >#Y
Therefore, M1 decides L1. ■

#### 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."
You have to be clear about
• 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.
Theorem 5.4.2: The following problems are undecidable for Turing Machines:
1. H0: Given TM M and string w, does M halt on w?
2. H1: Given TM M, does M halt on ε?
3. H2: Given TM M, does there exist a string w such that M halts on w, i.e., is L(M) = ∅?
4. H3: Given TM M, does M halt on all strings w, i.e., is L(M) = Σ*?
5. H4: Given TMs M1 and M2, do they accept the same languages, i.e., is L(M1) = L(M2)?
6. H5: Given TM M, is L(M) regular, context-free, recursive?
7. There is a specific TM M0 for which the problem is undecidable: given w, does M0 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 H1 = { E(M): M↓ε } ⊆ {1,c}*.

Instances of H1 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) ) = Mw
```
where Mw is the machine:
Mw: copy w onto the tape, then behave like M.
Our claim is that
```M↓w if and only if Mw↓ε
```
```[ (s,#) ⊢* (-,#w) ]  M
```
From a language perspective, the mapping is f:{1,c}* ⇾ {1,c}*:
```f( E(M,w) ) = E(Mw)
```
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 Mw
• create its encoding E(Mw)
Therefore, we have reduced from the halting problem, implying that this new problem, H1, is undecidable.
• (b) ⇾ (c) (H1 ⇾ H2), and, (b) ⇾ (d) (H1 ⇾ H3)

Instances of H1 are TMs (M) which halt on the empty string.

Instances of H2 are TMs (M) which halt on the some string.

Instances of H3 are TMs (M) which halt on the all strings.

One transformation function works for both cases:
```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 H1 to H2 (c) or H1 to H3 (d).

M′ simply ignores whatever string is put on the tape by erasing it. Our claim is that
```M↓ε if and only if M′↓w, for all w
```
and
```M↓ε if and only if M′↓w, for some w
```
• (d) ⇾ (e): Reduce H3 to H4.

Instances of H3 are TMs, (M), which halt on all strings.

Instances of H4 are TM pairs (M1,M2) which accept the same language.

The transformation is:
```f( M ) = (M, A)
```
where A is the Turing Machine which accepts all strings. Then
```M accepts all strings
if and only if
M and A accept the same set of strings (because A accepts all strings)
```
• (b) ⇾ (f): Reduce H1 to H5. Instances in both are single TMs.

Instances of H1 are TMs which halt on the empty string. The reduction is this:
```f( M ) = M′
```
Make M′ be a 4-tape machine which works like this:
```>(#x, >#, >#, >#)
```
2. Copy x to tape 2, then erase tape 1.
```(>#, >#x, >#, >#)
```
3. Behave like M on tape 1 (with empty input).
4. If M halts, behave like the universal TM, U on tapes 2,3,4.

Recall the definition of HALT = { E(M,w): M ↓ w } and that the Universal machine U accepts this language. Then
```M↓ε  ⇔  L(M′) = HALT    (neither regular, context-free, recursive)
M↑ε  ⇔  L(M′) = ∅       (regular, context-free, 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.
The same holds true replacing "regular", by either "context free" or "recursive".
• (g): M0 is the Universal TM, U. The strings which it cannot decide are E(M,w).