Examples of Unsolvable Problems

What are Unsolvable Problems?

Unsolvable (Undecidable) problems are problems for which no algorithm exists that always gives correct answer.

Simple Analogy

Think of it like:

Unsolvable: “Will I be happy tomorrow?” (can’t predict with certainty)
Solvable: “Is 7 prime?” (can always compute)

Not about:

Hard problems (may take long but solvable)
Unknown solutions (we don’t know yet)

About: Fundamentally impossible (no algorithm possible)

Why Unsolvable Problems Exist

Counting Argument

TMs: Countably infinite (can list them)

Languages: Uncountably infinite (2^Σ*)

Consequence: More languages than TMs!

Therefore: Most languages have no TM (not even recognizable)

Diagonalization

Self-reference creates paradox:

TM can take TM as input
Can construct “opposite” TM
Leads to contradiction
Shows some problems undecidable

Problem 1: Halting Problem

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

Problem Statement

Input: TM M and string w

Question: Does M halt on w?

Answer: Undecidable!

Why Undecidable?

Proof by contradiction:

Assume H decides HALT

Construct D that does opposite:

D(⟨M⟩):
  If H(⟨M⟩, ⟨M⟩) accepts:  loop
  If H(⟨M⟩, ⟨M⟩) rejects:  halt

Ask: Does D(⟨D⟩) halt?
Both cases lead to contradiction!
H cannot exist

Practical Impact

Can’t automatically:

Detect infinite loops in programs
Guarantee program termination
Verify absence of hangs

Must use: Testing, timeouts, heuristics

Status

Undecidable: ✗
Recognizable: ✓ (can simulate and wait)
Co-recognizable: ✗ (complement not recognizable)

Problem 2: Acceptance Problem

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

Problem Statement

Input: TM M and string w

Question: Does M accept w?

Answer: Undecidable!

Reduction from HALT

Given ⟨M, w⟩, construct M’:

M'(w):
  1. Simulate M on w
  2. If M halts and accepts: accept
  3. If M halts and rejects: accept
  4. If M loops: loop

Observe:

M halts on w ⟺ M’ accepts w
HALT reduces to Aₜₘ
Aₜₘ undecidable!

Why Important?

Can’t automatically verify:

Does program produce output?
Does program reach certain state?
Does program satisfy specification?

Status

Undecidable: ✗
Recognizable: ✓ (simulate M on w)
Co-recognizable: ✗

Problem 3: Emptiness Problem

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

Problem Statement

Input: TM M

Question: Does M accept nothing?

Answer: Undecidable!

Reduction from Aₜₘ

Given ⟨M, w⟩, construct M’:

M'(x):
  1. Ignore input x
  2. Simulate M on w
  3. If M accepts w: accept x
  4. If M rejects/loops: reject x

Observe:

M accepts w ⟺ L(M’) = Σ* (non-empty)
M doesn’t accept w ⟺ L(M’) = ∅ (empty)
Aₜₘ reduces to Ēₜₘ (complement)
Eₜₘ undecidable!

Practical Impact

Can’t decide:

Does program produce any output?
Is function dead code?
Is language empty?

Status

Undecidable: ✗
Recognizable: ✗ (complement of RE problem)
Co-recognizable: ✓

Problem 4: Equivalence Problem

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

Problem Statement

Input: Two TMs M₁ and M₂

Question: Do they accept the same language?

Answer: Undecidable!

Reduction from Eₜₘ

Given ⟨M⟩, construct M_empty that rejects everything:

M_empty(x): reject

Check: L(M) = L(M_empty)?

Observe:

L(M) = ∅ ⟺ L(M) = L(M_empty)
Eₜₘ reduces to EQₜₘ
EQₜₘ undecidable!

Practical Impact

Can’t automatically verify:

Do two programs compute same function?
Is optimization correct?
Are two implementations equivalent?

Status

Undecidable: ✗
Recognizable: ✗
Co-recognizable: ✗ (neither side recognizable!)

Problem 5: Regularity Problem

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

Problem Statement

Input: TM M

Question: Is L(M) a regular language?

Answer: Undecidable!

Proof by Rice’s Theorem

Property P: “L is regular”

Non-trivial:

∅ is regular (has property)
Σ* is regular (has property)
{aⁿbⁿ} not regular (doesn’t have property)

Rice’s theorem: Any non-trivial property undecidable

REGₜₘ undecidable!

Alternative Reduction

Given ⟨M, w⟩, construct M’:

M'(x):
  1. If x = aⁿbⁿ: accept
  2. Otherwise:
       Simulate M on w
       If M accepts w: accept x
       If M rejects/loops: reject x

Observe:

M accepts w ⟺ L(M’) = Σ* (regular)
M doesn’t accept w ⟺ L(M’) = {aⁿbⁿ} (not regular)
Aₜₘ reduces to REGₜₘ

Status

Undecidable: ✗
Recognizable: ✗
Co-recognizable: ✗

Problem 6: Context-Free Problem

CFLₜₘ = {⟨M⟩ | L(M) is context-free}

Problem Statement

Input: TM M

Question: Is L(M) context-free?

Answer: Undecidable!

Proof

Rice’s theorem: Property of language

Non-trivial:

∅ is CFL
{aⁿbⁿcⁿ} not CFL

CFLₜₘ undecidable!

Status

Undecidable: ✗
Recognizable: ✗
Co-recognizable: ✗

Problem 7: Totality Problem

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

Problem Statement

Input: TM M

Question: Does M always terminate?

Answer: Undecidable!

Reduction from HALT

Given ⟨M, w⟩, construct M’:

M'(x):
  1. If x = w:
       Simulate M on w
       (halt if M halts, loop if M loops)
  2. If x ≠ w:
       Halt immediately

Observe:

M halts on w ⟺ M’ halts on all inputs
HALT reduces to TOTₜₘ
TOTₜₘ undecidable!

Practical Impact

Can’t verify:

Does program always terminate?
Is there no infinite loop?
Is recursion always finite?

Status

Undecidable: ✗
Recognizable: ✗
Co-recognizable: ✓

Problem 8: Finiteness Problem

FINₜₘ = {⟨M⟩ | L(M) is finite}

Problem Statement

Input: TM M

Question: Does M accept finitely many strings?

Answer: Undecidable!

Proof

Rice’s theorem: Non-trivial property

Examples:

L = {a} is finite
L = a* is infinite

FINₜₘ undecidable!

Status

Undecidable: ✗
Recognizable: ✗
Co-recognizable: ✗

Problem 9: Membership for Fixed String

Lw = {⟨M⟩ | M accepts w} (for fixed w)

Problem Statement

Input: TM M

Question: Does M accept specific string w?

Answer: Undecidable!

Reduction from Aₜₘ

Given ⟨M, w⟩, construct M’:

M'(x):
  1. Ignore input x
  2. Simulate M on w
  3. Accept if M accepts w

Observe:

M accepts w ⟺ M’ accepts any string
Aₜₘ reduces to membership
Undecidable!

Status

Undecidable: ✗
Recognizable: ✓
Co-recognizable: ✗

Problem 10: Grammar Ambiguity

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

Problem Statement

Input: Context-free grammar G

Question: Does G have string with multiple parse trees?

Answer: Undecidable!

Why Undecidable?

Reduction: Complex reduction from Post Correspondence Problem

Intuition:

Can encode computation in parse trees
Multiple parses = multiple computations
Can simulate undecidable problem

Practical Impact

Can’t automatically:

Check if grammar ambiguous
Detect parser conflicts
Verify unique interpretation

Must use: Grammar analysis tools (incomplete)

Status

Undecidable: ✗
For some subclasses decidable

Problem 11: Post Correspondence Problem (PCP)

Problem Statement

Input: Finite set of tile pairs

Domino set:
┌─────┬─────┬─────┐
│ top │ top │ top │
│  1  │  2  │  3  │
├─────┼─────┼─────┤
│ bot │ bot │ bot │
│  1  │  2  │  3  │
└─────┴─────┴─────┘

Question: Can you select dominoes (with repetition) so top sequence = bottom sequence?

Example:

Dominoes:
  ┌───┐  ┌───┐  ┌───┐
  │ a │  │ ab│  │ ba│
  ├───┤  ├───┤  ├───┤
  │ ab│  │ b │  │ a │
  └───┘  └───┘  └───┘

Solution: Use 1, 2, 1

Top:    a  ab  a  = aaba
Bottom: ab  b ab = abab
Not a match!

Try: 2, 1, 3
Top:    ab a ba = ababa
Bottom:  b ab a = ababa
Match! ✓

Why Undecidable?

Proved by: Emil Post (1946)

Reduction: From halting problem

Key idea: Encode TM computation as string matching

Applications

Used to prove other problems undecidable:

Grammar ambiguity
Context-free equivalence
Many language problems

Problem 12: Tiling Problems

Wang Tiles

Input: Finite set of square tiles with colored edges

Question: Can you tile infinite plane with these tiles?

Tiles cannot be rotated
Adjacent edges must match colors

Answer: Undecidable!

Domino Problem

Similar: Tile infinite board with dominoes

Undecidable: Proved by Wang (1961)

Problem 13: Program Verification

Does Program Satisfy Specification?

Input: Program P and specification S

Question: Does P satisfy S for all inputs?

Answer: Undecidable!

Reason: Can encode halting problem

Does Program Have Bug?

Input: Program P

Question: Does P have any bug?

Answer: Undecidable!

Reason: “Bug” is semantic property

Problem 14: Rice’s Theorem Applications

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

Quick Undecidability Proofs

All undecidable by Rice:

Is L(M) = ∅? ✗
Is L(M) infinite? ✗
Is L(M) = Σ*? ✗
Does L(M) contain ε? ✗
Is L(M) regular? ✗
Is L(M) context-free? ✗
Is |L(M)| = 5? ✗
Is L(M) decidable? ✗
Does L(M) contain “hello”? ✗
Is L(M) = L(M’)? ✗

Decidable (Not Covered by Rice)

About M itself, not L(M):

Does M have 5 states? ✓
Does ⟨M⟩ contain ‘a’? ✓
Is |⟨M⟩| = 100? ✓
Does M have start state q₀? ✓

Summary of Unsolvable Problems

Problem	Recognizable	Co-Recognizable	Undecidable
HALT	✓	✗	✗
Aₜₘ	✓	✗	✗
Eₜₘ	✗	✓	✗
EQₜₘ	✗	✗	✗
REGₜₘ	✗	✗	✗
CFLₜₘ	✗	✗	✗
TOTₜₘ	✗	✓	✗
FINₜₘ	✗	✗	✗
AMBcfg	?	?	✗
PCP	✓	✗	✗

Why These Problems Matter

1. Theoretical Limits

Shows: Fundamental limits of computation

Can’t solve: Even with infinite time and memory

Not about: Current technology limitations

2. Practical Impact

Can’t automate:

Bug detection (complete)
Program verification (general)
Optimization verification
Security analysis (complete)

Must use: Heuristics, testing, human reasoning

3. Tool Development

Static analysis: Must be conservative

Type systems: Decidable approximations

Verification tools: Limited scope

Strategies for Proving Undecidability

1. Diagonalization

Direct proof: Construct paradoxical machine

Used for: HALT, Aₜₘ

2. Reduction

Reduce from known undecidable: A ≤ₘ B

Most common: Reduce from HALT or Aₜₘ

3. Rice’s Theorem

Check if property is:

Non-trivial (some have it, some don’t)
Semantic (depends on L(M), not M)

If yes: Undecidable!

4. Universal Problem

Prove problem is universal: Every RE reduces to it

Then: Must be undecidable

Important Exam Points

✓ HALT undecidable: Can’t decide if TM halts
✓ Aₜₘ undecidable: Can’t decide if TM accepts
✓ Eₜₘ undecidable: Can’t decide if language empty
✓ EQₜₘ undecidable: Can’t decide equivalence
✓ Rice’s theorem: Non-trivial properties undecidable
✓ Reduction technique: Prove B undecidable via A ≤ B
✓ Diagonalization: Self-reference creates paradox
✓ PCP undecidable: Tile matching problem
✓ AMBcfg undecidable: Grammar ambiguity
✓ TOTₜₘ undecidable: Can’t decide termination

Common Mistakes to Avoid

✗ Mistake 1: Thinking undecidable = very hard
✓ Correct: Undecidable = impossible (not just hard)

✗ Mistake 2: Can solve with more powerful computer
✓ Correct: No algorithm exists (even ideal computer)

✗ Mistake 3: All problems undecidable
✓ Correct: Many problems decidable (e.g., arithmetic)

✗ Mistake 4: Undecidable = no solutions exist
✓ Correct: Can solve specific instances, not general

✗ Mistake 5: Rice’s theorem applies to all properties
✓ Correct: Only semantic properties (of L(M))

✗ Mistake 6: Can approximate undecidable problems perfectly
✓ Correct: Approximations incomplete or unsound

Practice Questions

Q1: Is halting problem decidable?

Answer: No! Proved undecidable by Turing.

Q2: How to prove problem undecidable?

Answer: Reduction from HALT or use Rice’s theorem.

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

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

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

Answer: Yes! Syntactic property, not semantic.

Q5: What is PCP?

Answer: Post Correspondence Problem (tile matching).

Q6: Is grammar ambiguity decidable?

Answer: No! AMBcfg undecidable.

Q7: Can we verify programs automatically?

Answer: Not in general (undecidable), only special cases.

Q8: Is equivalence of TMs decidable?

Answer: No! EQₜₘ undecidable.

Q9: What problems are decidable?

Answer: Many! Arithmetic, DFA properties, CFG parsing, etc.

Q10: Why does undecidability matter?

Answer: Shows fundamental limits of computation and automation.

Summary

Unsolvable: Problems no algorithm can solve
HALT: Can’t decide if TM halts (most famous)
Aₜₘ: Can’t decide if TM accepts
Eₜₘ: Can’t decide if language empty
EQₜₘ: Can’t decide if languages equivalent
Rice’s theorem: All non-trivial properties undecidable
Reduction: Main proof technique (A ≤ B)
Diagonalization: Self-reference creates paradox
PCP: Undecidable tiling problem
Practical impact: Limits of software verification
Many undecidable: REGₜₘ, CFLₜₘ, TOTₜₘ, FINₜₘ, AMBcfg
Key insight: Fundamental limits exist

Unsolvable problems reveal the boundaries of algorithmic computation!