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

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: You have to be clear about

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


© Robert M. Kline