Decidability and Halting Problem

What is Decidability?

Decidability asks: Can we write a program that always gives correct yes/no answer?

Simple Analogy

Think of it like:

Traffic light: Always shows green or red (never stuck)
Magic 8-ball: May say “ask again later” (not decidable!)
Calculator: Always gives answer (decidable)
Infinite loop: Never answers (not decidable)

Formal Definition

Problem is decidable if there exists TM M such that:

M halts on all inputs
M accepts ⟺ answer is “yes”
M rejects ⟺ answer is “no”

Key: Always terminates with correct answer!

Examples of Decidable Problems

1. Is number n even?

Input: n

Question: Is n even?

TM:

1. Read n in binary
2. Check last bit
3. Accept if 0 (even)
4. Reject if 1 (odd)

Always halts: Yes ✓

2. Is string in {aⁿbⁿ | n ≥ 0}?

Input: w

Question: Does w have equal a’s and b’s, a’s first?

TM:

1. Mark one a with X
2. Find and mark one b with Y
3. Repeat until all matched
4. Accept if all matched
5. Reject if mismatch

Always halts: Yes ✓

3. Does DFA M accept string w?

Input: ⟨M, w⟩ (DFA M and string w)

Question: Does M accept w?

TM:

1. Simulate M on w
2. DFA always halts (no loops)
3. Accept if M accepts
4. Reject if M rejects

Always halts: Yes ✓ (DFA has no infinite paths)

4. Is DFA language empty?

Input: ⟨M⟩ (DFA M)

Question: Is L(M) = ∅?

TM:

1. Check if accept state reachable from start
2. Use graph search (BFS/DFS)
3. Reject if reachable (language non-empty)
4. Accept if unreachable (language empty)

Always halts: Yes ✓

5. Are two DFAs equivalent?

Input: ⟨M₁, M₂⟩

Question: Is L(M₁) = L(M₂)?

TM:

1. Construct DFA for (L(M₁) \ L(M₂)) ∪ (L(M₂) \ L(M₁))
2. Check if this DFA's language is empty
3. Accept if empty (equivalent)
4. Reject if non-empty (different)

Always halts: Yes ✓

The Halting Problem

Most famous undecidable problem!

Problem Statement

HALT = {⟨M, w⟩ | TM M halts on input w}

Question: Given TM M and input w, does M halt on w?

Answer: Sometimes loops, sometimes halts - can we always tell?

Why Important?

If HALT decidable:

Could check if any program terminates
No infinite loops!
Software verification easy
Compiler optimizations perfect

Reality: HALT undecidable!

Consequence: Can’t always tell if program terminates

Proof: Halting Problem Undecidable

Proof by contradiction (Turing, 1936)

Assumptions

Assume: TM H decides HALT

H(⟨M, w⟩) = accept if M halts on w
          = reject if M loops on w

H always halts and gives correct answer.

Construction

Build new TM D (“Diagonalizer”):

D(⟨M⟩):
  1. Run H(⟨M, ⟨M⟩⟩)
  2. If H accepts (M halts on ⟨M⟩):
       Loop forever
  3. If H rejects (M loops on ⟨M⟩):
       Halt and accept

D does opposite:

If M halts on ⟨M⟩, D loops on ⟨M⟩
If M loops on ⟨M⟩, D halts on ⟨M⟩

The Paradox

Ask: Does D(⟨D⟩) halt?

Case 1: D halts on ⟨D⟩

Then H(⟨D, ⟨D⟩⟩) accepts
So by line 2-3, D loops on ⟨D⟩
Contradiction! D both halts and loops

Case 2: D loops on ⟨D⟩

Then H(⟨D, ⟨D⟩⟩) rejects
So by line 4-5, D halts on ⟨D⟩
Contradiction! D both loops and halts

Conclusion

Both cases lead to contradiction

Therefore: Our assumption wrong!

H cannot exist

HALT is undecidable ✗

Understanding the Proof

Self-Reference

Key idea: TM can take TM as input

D(⟨M⟩): Input is description of M

D(⟨D⟩): Feed D its own description!

Like: “This sentence is false” paradox

Diagonalization

Imagine table:

        ⟨M₁⟩  ⟨M₂⟩  ⟨M₃⟩  ⟨M₄⟩  ...
M₁      H      L      H      L     ...
M₂      L      H      H      H     ...
M₃      H      H      L      H     ...
M₄      L      L      H      H     ...
...

H = halts, L = loops

Diagonal: M₁(⟨M₁⟩), M₂(⟨M₂⟩), M₃(⟨M₃⟩), …

D differs from all:

D(⟨M₁⟩) ≠ M₁(⟨M₁⟩)
D(⟨M₂⟩) ≠ M₂(⟨M₂⟩)
D(⟨M₃⟩) ≠ M₃(⟨M₃⟩)
…

But D is also a TM: Should be in table!

Contradiction: Can’t fit D in table

Why Can’t We Just Test?

Q: Can’t we run M on w and see if it halts?

A: What if M loops? We wait forever!

Can’t tell difference:

M running for long time (will eventually halt)
M looping forever (never halts)

No time bound: Can’t just wait N steps

Variants of Halting Problem

1. Does M halt on empty input?

HALT₀ = {⟨M⟩ | M halts on ε}

Undecidable! (Reduction from HALT)

2. Does M halt on all inputs?

HALT∀ = {⟨M⟩ | M halts on all inputs}

Undecidable! (Rice’s theorem)

3. Does M halt on some input?

HALT∃ = {⟨M⟩ | M halts on at least one input}

Undecidable! (Rice’s theorem)

4. Does M accept input w?

Aₜₘ = {⟨M, w⟩ | M accepts w}

Undecidable! (Reduction from HALT)

Actually: Aₜₘ ≡ₘ HALT (equivalent)

Recognizable but Not Decidable

HALT is recognizable!

TM Recognizing HALT

M_recognize(⟨M, w⟩):
  1. Simulate M on w
  2. If M halts, accept
  3. If M loops, we also loop

Accepts all in HALT: Yes ✓

Halts on all inputs: No ✗ (loops if M loops)

Therefore: HALT is recognizable but not decidable

Complement Not Recognizable

H̄ALT = {⟨M, w⟩ | M does not halt on w}

H̄ALT is NOT recognizable!

Proof: If both HALT and H̄ALT recognizable, then HALT decidable (contradiction)

Consequence:

HALT: Recognizable, not decidable
H̄ALT: Not even recognizable!

Reduction Technique

To prove problem B undecidable:

Take known undecidable A (e.g., HALT)
Show A ≤ₘ B (A reduces to B)
Conclude B undecidable

Logic: If B decidable, then A decidable (contradiction)

Example: Acceptance Problem

Aₜₘ = {⟨M, w⟩ | M accepts w}

Claim: Aₜₘ undecidable

Proof: Reduce HALT to Aₜₘ

Given ⟨M, w⟩, construct M’:

M'(w):
  1. Simulate M on w
  2. If M halts:
       Accept
  3. If M loops:
       (M' also loops)

Observe:

M halts on w ⟺ M’ accepts w
M loops on w ⟺ M’ loops on w

M accepts w: Always (if it halts)

Therefore: HALT ≤ₘ Aₜₘ

Conclusion: Aₜₘ undecidable

Examples of Undecidable Problems

1. Emptiness Problem

Eₜₘ = {⟨M⟩ | L(M) = ∅}

Question: Does M accept nothing?

Undecidable! (Rice’s theorem)

2. Equivalence Problem

EQₜₘ = {⟨M₁, M₂⟩ | L(M₁) = L(M₂)}

Question: Do M₁ and M₂ accept same language?

Undecidable! (Rice’s theorem)

3. Totality Problem

TOTₜₘ = {⟨M⟩ | M halts on all inputs}

Question: Does M always terminate?

Undecidable! (Rice’s theorem)

4. Regularity Problem

REGₜₘ = {⟨M⟩ | L(M) is regular}

Question: Does M accept regular language?

Undecidable! (Rice’s theorem)

5. Ambiguity Problem

AMBcfg = {⟨G⟩ | CFG G is ambiguous}

Question: Does grammar have multiple parse trees?

Undecidable! (Reduction proof)

6. Post Correspondence Problem

PCP: Given tile pairs, can you match top and bottom?

Undecidable! (Famous reduction target)

Rice’s Theorem Application

Rice’s Theorem: Any non-trivial property of recognizable languages is undecidable.

Non-trivial: Some TMs have it, some don’t

Quick Undecidability Proofs

Is L(M) empty? Property of L(M) → Undecidable!

Is L(M) infinite? Property of L(M) → Undecidable!

Is L(M) = {hello}? Property of L(M) → Undecidable!

Does L(M) contain ε? Property of L(M) → Undecidable!

Is L(M) context-free? Property of L(M) → Undecidable!

Decidable Properties (Not Covered by Rice)

Does M have 5 states? About M itself → May be decidable

Does ⟨M⟩ contain symbol ‘a’? About encoding → Decidable

Does M have start state q₀? Syntactic → Decidable

Practical Implications

1. Software Verification

Can’t automatically verify:

Does program terminate?
Does program meet specification?
Is program bug-free?

Must use:

Testing (incomplete)
Formal methods (limited)
Human reasoning

2. Compiler Optimization

Can’t decide:

Is code dead (unreachable)?
Are two programs equivalent?
Can loop be parallelized?

Must use: Conservative heuristics

3. Security

Can’t automatically determine:

Does program contain malware?
Is program secure?
Does program leak data?

Must use: Static analysis (approximate)

4. Program Analysis

Undecidable questions:

Does variable always have positive value?
Does array access stay in bounds?
Does pointer never become null?

Rice’s theorem: Any semantic property

Degrees of Unsolvability

Not all undecidable problems equally hard!

Turing Degrees

Ordering: A ≤ₜ B (A Turing-reduces to B)

Degrees form hierarchy:

0 (decidable)
  ↓
0' (HALT)
  ↓
0'' (Halting of halting problem)
  ↓
...

Arithmetical Hierarchy

Σ₀ = Π₀: Decidable (recursive)

Σ₁: RE (recognizable)

Example: HALT

Π₁: Co-RE (complement recognizable)

Example: H̄ALT (complement)

Σ₂, Π₂, …: Higher levels

Important Exam Points

✓ Decidable: TM always halts with correct answer
✓ HALT undecidable: Can’t always tell if TM halts
✓ Diagonalization: Proof technique via self-reference
✓ D(⟨D⟩): Paradox shows H can’t exist
✓ HALT recognizable: Can simulate and accept if halts
✓ H̄ALT not recognizable: Can’t recognize non-halting
✓ Reduction: Prove B undecidable via A ≤ B
✓ Rice’s theorem: Non-trivial properties undecidable
✓ Aₜₘ ≡ HALT: Acceptance equivalent to halting
✓ Many problems undecidable: Eₜₘ, EQₜₘ, TOTₜₘ, etc.

Common Mistakes to Avoid

✗ Mistake 1: Thinking halting decidable
✓ Correct: HALT undecidable (Turing’s theorem)

✗ Mistake 2: Can just wait and see if halts
✓ Correct: Can’t tell loop from slow computation

✗ Mistake 3: H̄ALT also recognizable
✓ Correct: H̄ALT not even recognizable!

✗ Mistake 4: All TM properties undecidable
✓ Correct: Only semantic properties (Rice’s theorem)

✗ Mistake 5: Confusing D and H
✓ Correct: H (assumed) decides HALT, D contradicts

✗ Mistake 6: Thinking undecidable = unsolvable
✓ Correct: Can solve specific instances, not all

Practice Questions

Q1: What is halting problem?

Answer: Given TM M and input w, decide if M halts on w.

Q2: Is halting problem decidable?

Answer: No! Proved undecidable by Turing (1936).

Q3: What is key idea in halting problem proof?

Answer: Self-reference (D runs on ⟨D⟩) creates contradiction.

Q4: Is HALT recognizable?

Answer: Yes! Simulate M on w, accept if halts.

Q5: Is complement of HALT recognizable?

Answer: No! If both sides recognizable, HALT would be decidable.

Q6: What is Rice’s theorem?

Answer: Any non-trivial property of RE languages undecidable.

Q7: How to prove problem undecidable?

Answer: Reduce from known undecidable (e.g., HALT).

Q8: Is “Does M have 5 states?” decidable?

Answer: Yes! Syntactic property, not semantic.

Q9: Is “Is L(M) empty?” decidable?

Answer: No! Non-trivial property (Rice’s theorem).

Q10: Why can’t we solve halting problem?

Answer: Self-reference creates logical contradiction.

Summary

Decidable: TM always halts with correct answer
Halting problem: {⟨M, w⟩ | M halts on w}
HALT undecidable: Proved by contradiction via diagonalization
Diagonalizer D: Does opposite of H’s prediction
D(⟨D⟩) paradox: Both halts and loops (contradiction)
Self-reference: Key to proof (TM taking TM as input)
HALT recognizable: Simulate and accept if halts
H̄ALT not recognizable: Can’t recognize non-halting
Reduction: Prove undecidability via A ≤ B
Rice’s theorem: Non-trivial properties undecidable
Many undecidable: Aₜₘ, Eₜₘ, EQₜₘ, TOTₜₘ, REGₜₘ
Practical impact: Limits of software verification

Halting problem reveals fundamental limits of computation!

Decidability and Halting Problem

What is Decidability?

Simple Analogy

Formal Definition

Examples of Decidable Problems

1. Is number n even?

2. Is string in {aⁿbⁿ | n ≥ 0}?

3. Does DFA M accept string w?

4. Is DFA language empty?

5. Are two DFAs equivalent?

The Halting Problem

Problem Statement

Why Important?

Proof: Halting Problem Undecidable

Assumptions

Construction

The Paradox

Conclusion

Understanding the Proof

Self-Reference

Diagonalization

Why Can’t We Just Test?

Variants of Halting Problem

1. Does M halt on empty input?

2. Does M halt on all inputs?

3. Does M halt on some input?

4. Does M accept input w?

Recognizable but Not Decidable

TM Recognizing HALT

Complement Not Recognizable

Reduction Technique

Example: Acceptance Problem

Examples of Undecidable Problems

1. Emptiness Problem

2. Equivalence Problem

3. Totality Problem

4. Regularity Problem

5. Ambiguity Problem

6. Post Correspondence Problem

Rice’s Theorem Application

Quick Undecidability Proofs

Decidable Properties (Not Covered by Rice)

Practical Implications

1. Software Verification

2. Compiler Optimization

3. Security

4. Program Analysis

Degrees of Unsolvability

Turing Degrees

Arithmetical Hierarchy

Important Exam Points

Common Mistakes to Avoid

Practice Questions

Summary

Install Notes App