The diagonal language and the halting problem

1. Is P(Σ*) countable?
   Stuck? Peek at 5.1 Countable vs uncountable; diagonalization

   • Countable = finite or bijection with ℕ (listable). Σ*, ℕ×ℕ, TMs, RE, CFG, regular languages: countable.
   • P(ℕ), P(Σ*) (all languages), infinite binary sequences, ℝ: uncountable (diagonal).
   • Countably many TMs ⇒ most languages are not RE.

   Read lesson 5.1

2. What does the universal TM do?
   Stuck? Peek at 4.4 Encoding TMs, the universal TM, and the Church–Turing thesis

   • ⟨M⟩: binary code of transitions (0ⁱ1 0ʲ1 0ᵏ1 0ˡ1 0ᵐ, separated by 11). TMs are countable.
   • Universal TM U: simulates M on w; L(U) = {⟨M,w⟩ : M accepts w} is RE.
   • Church–Turing thesis: algorithm ⇔ TM (thesis, not theorem).

   Read lesson 4.4

3. L is RE but not recursive. What is L̅?
   Stuck? Peek at 4.3.3 Closure of REC and RE; L and L̅ both RE ⇒ L recursive

   • REC closed: ∪ ∩ complement − concat * reversal h⁻¹; not h.
   • RE closed: ∪ ∩ concat * reversal h h⁻¹; not complement, not difference.
   • L, L̅ ∈ RE ⇒ L ∈ REC. L ∈ RE − REC ⇒ L̅ ∉ RE.

   Read lesson 4.3.3

Every programmer has wished for a tool that looks at code and says “this will hang”. Turing proved in 1936 that no such tool can work correctly on all programs. The proof is a diagonal argument that turns any claimed halting-checker against itself. This lesson builds the three named languages GATE asks about: L_d (not RE), A_TM and HALT_TM (RE but undecidable).

Suppose a program H(P, x) always correctly says whether program P halts on input x. Write D(P): “if H says P halts on input P, loop forever; otherwise halt.” What happens when you run D on D?

Prediction check

If D(D) halts, then H said D does not halt on D — wrong. If D(D) loops, then H said D halts on D — wrong. Either way H is wrong on (D, D). So no correct H exists.

The diagonal language L_d

List all strings w₁, w₂, … and all TMs M₁, M₂, … (TM Mᵢ has code wᵢ).

L_d is not RE. If L_d = L(Mₖ) for some k, ask whether wₖ ∈ L_d: wₖ ∈ L_d ⇔ wₖ ∉ L(Mₖ) = L_d. Contradiction. Its complement, { wᵢ : Mᵢ accepts wᵢ }, is RE (simulate Mᵢ on wᵢ), so L_d is co-RE.

A_TM: acceptance is RE but not recursive

RE: the universal TM recognizes it. Not recursive: if a decider H for A_TM existed, build D(⟨M⟩) = accept iff H rejects ⟨M, ⟨M⟩⟩. Then D accepts ⟨D⟩ ⇔ H rejects ⟨D, ⟨D⟩⟩ ⇔ D does not accept ⟨D⟩. Contradiction. ∎

Consequence (4.3.3): the complement of A_TM is not RE.

HALT_TM: the halting problem

RE (simulate and accept when it halts) but undecidable: a halting decider would decide A_TM (first check M halts on w, then simulate safely). Its complement is not RE.

Where they sit

Recursive = RE ∩ co-RE (both a language and its complement recognizable).

Putting it together

• Diagonalizing against TMs gives L_d, which no TM recognizes.
• A_TM and HALT_TM are recognizable but undecidable; their complements are not RE.
• Recursive = RE ∩ co-RE.

language                     RE?    co-RE?   recursive?
L_d                          no     yes      no
A_TM (L_u)                   yes    no       no
complement of A_TM           no     yes      no
HALT_TM                      yes    no       no
complement of HALT_TM        no     yes      no

Every new undecidability proof can now borrow these results: show that deciding your problem would decide A_TM. That move is called a reduction — next.

1. MSQ

   Which are RE?

   1. A_TM
   2. HALT_TM
   3. L_d
   4. complement of A_TM
2. MCQ

   Is HALT_TM decidable?

   1. yes
   2. no, but it is RE
   3. no, and it is not RE
   4. only for deterministic TMs
3. MCQ

   Recursive languages are exactly:

   1. RE
   2. co-RE
   3. RE ∩ co-RE
   4. RE ∪ co-RE
4. MCQ

   The complement of L_d is:

   1. not RE
   2. RE
   3. recursive
   4. regular

• diagonal language L_d
• A_TM (universal language L_u)
• HALT_TM (halting problem)
• undecidable
• co-RE
• REC = RE ∩ co-RE

1. Is A_TM RE? Recursive?
   Reveal answer

   RE yes, recursive no.
2. Is L_d RE?
   Reveal answer

   No (its complement is).
3. Is the complement of HALT_TM RE?
   Reveal answer

   No.
4. REC in terms of RE and co-RE?
   Reveal answer

   REC = RE ∩ co-RE.