10.2 The Halting Problem, Undecidability, Post Correspondence Problem & Rice's Theorem

Back to DBMS Notes

📚Module 01Topic 1.1⏱️24 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The Self-Referential Trap

Can a computer program analyze another computer program and tell you with 100% certainty what it will do?

• Can an automated grading tool inspect your Python code and guarantee: "This code will never get stuck in an infinite loop on any test case"?
• Can a compiler static analyzer verify: "This software will never access a null pointer, will never deadlock, and will compute the exact mathematical function specified"?

Every programmer has wished for such a tool. But in 1936, Alan Turing proved that such a general tool is mathematically impossible.

The barrier is not a lack of CPU speed, memory, or artificial intelligence. It is a fundamental, inescapable paradox of logic: Self-Reference.

🍳 The Everyday Analogy: The Town Barber & The Ultimate Lie

Consider two famous logical paradoxes that shatter everyday reasoning:

• The Barber Paradox (Bertrand Russell):
  In a small village, the town barber obeys a strict rule: "I shave all and only those men in town who do not shave themselves."
  The Paradox: Does the barber shave himself?
  • If he shaves himself, he violates the rule (he only shaves men who do not shave themselves).
  • If he does not shave himself, by rule he must shave himself!
• The Omniscient Prediction Machine:
  Imagine a fortune-teller machine that claims it can predict your next action with 100% accuracy. It prints a card saying: "You will raise your right hand in the next 5 seconds."
  Knowing this prediction, you immediately put both hands in your pockets and stand completely still! The prediction is broken.

Turing realized that if an algorithm existed that could predict whether any program halts, we could construct a spiteful adversarial program that asks what the algorithm predicts for itself, and then deliberately does the exact opposite.

💻 Bridging to Computer Science

In computer science, a decision problem is Undecidable if there is no algorithm that can solve it for all possible inputs in finite time.

1. The Halting Problem ($A_{\text{TM}}$ or $H_{\text{TM}}$): Determining whether an arbitrary Turing Machine $M$ halts on an arbitrary input $w$ is fundamentally UNDECIDABLE.
2. Rice's Theorem: Turing's halting barrier spreads like a contagion to all of software engineering. Rice's Theorem proves that ANY non-trivial semantic property of a program's behavior is undecidable (e.g. testing whether a program is bug-free, computes primes, or prints "Hello").
3. The Post Correspondence Problem (PCP): An innocent-looking domino string-matching puzzle that is mathematically undecidable, providing the ultimate bridge to prove that context-free grammar ambiguity is undecidable.

---

📑Table of Contents

• 🛑 Alan Turing's Halting Problem (A_TM)
  • The Formal Mathematical Proof by Diagonalization
• 🔗 Reductions: The Lever of Undecidability
  • Mapping Reductions (A ≤_m B)
• 🌾 Rice's Theorem: The Ultimate Bulldozer of Computability
  • Understanding Semantic Properties
  • Understanding Non-Trivial Properties
  • ⚠️ When Does Rice's Theorem NOT Apply? (Syntactic Properties)
• 🧩 The Post Correspondence Problem (PCP)
  • The Domino Tile Match Game
  • The PCP Undecidability Theorem
  • Why is PCP so Important?
• 🏭 Real-World Production Context: Antivirus Scanners & Security Auditing
  • Industrial Case Studies
• 📐 Numerical Applications & Worked Examples
  • Problem 1: Solving a Concrete Instance of the Post Correspondence Problem
  • Problem 2: Applying Rice's Theorem to Semantic Predicates
  • Problem 3: Proving Undecidability via Mapping Reduction (A_TM ≤_m HALT_TM)
• 🎯 Exam & Interview Pitfall Check

---

🛑 Alan Turing's Halting Problem (A_TM)

Let $A_{\text{TM}}$ be the language of all (Machine, String) pairs where machine $M$ accepts input $w$:

$A_{\text{TM}} = \{ \langle M, w \rangle \mid M \text{ is a Turing Machine and } M \text{ accepts } w \}$

Turing's Master Theorem (1936):
$A_{\text{TM}}$ is UNDECIDABLE (Not Recursive). There is no Turing Machine that can decide $A_{\text{TM}}$ and halt on all inputs.

Architecture Flow

Alan Turing's Diagonalization Contradiction Proof

The 4-stage mathematical proof showing that a universal halting decider destroys itself

🏛️Hypothesis

Assume Decider H Exists

Assume there exists a halting decider H(⟨M, w⟩) that always halts: outputs YES if M accepts w; NO if M rejects/loops.

→

Construct Adversary

😈The Saboteur

Adversarial Machine D

Construct machine D with input ⟨M⟩. D runs H on ⟨M, ⟨M⟩⟩ and does the exact OPPOSITE of H's verdict.

→

Self-Feeding

🔄Self-Reference

Feed D into D: D(⟨D⟩)

Feed machine D its own source code as input: execute D(⟨D⟩). What does D do?

→

Evaluate Paradox

💥Fatal Contradiction

Mathematical Collapse

If D halts ⇒ H predicted NO ⇒ D was supposed to loop! If D loops ⇒ H predicted YES ⇒ D was supposed to halt! H CANNOT EXIST.

The Formal Mathematical Proof by Diagonalization

1. Assume for contradiction that $A_{\text{TM}}$ is decidable by some Turing Machine $H$:

$H(\langle M, w \rangle) = \begin{cases} \mathbf{ACCEPT} & \text{if } M \text{ accepts } w \\ \mathbf{REJECT} & \text{if } M \text{ does not accept } w \text{ (rejects or loops)} \end{cases}$

2. Construct an adversarial Turing Machine $D$ that takes as input the description of an arbitrary Turing Machine $\langle M \rangle$:
   • $D$ runs $H$ on the input $\langle M, \langle M \rangle \rangle$ (feeding $M$ its own source code).
   • Inversion Logic:
     • If $H(\langle M, \langle M \rangle \rangle)$ outputs ACCEPT, then $D$ LOOPS FOREVER!
     • If $H(\langle M, \langle M \rangle \rangle)$ outputs REJECT, then $D$ HALTS AND ACCEPTS!

$D(\langle M \rangle) = \begin{cases} \mathbf{LOOP \; FOREVER} & \text{if } M \text{ accepts } \langle M \rangle \\ \mathbf{ACCEPT} & \text{if } M \text{ does not accept } \langle M \rangle \end{cases}$

3. The Self-Referential Trap: Now run $D$ with its own source code $\langle D \rangle$ as input:

$D(\langle D \rangle) = \begin{cases} \mathbf{LOOP \; FOREVER} & \text{if } D \text{ accepts } \langle D \rangle \\ \mathbf{ACCEPT} & \text{if } D \text{ does not accept } \langle D \rangle \end{cases}$

4. The Impossible Contradiction:
   • Scenario 1: Suppose $D$ accepts $\langle D \rangle$. Then by looking at the definition of $D$, $D$ must loop forever! A contradiction.
   • Scenario 2: Suppose $D$ does not accept $\langle D \rangle$. Then by the definition of $D$, $D$ must accept! Another contradiction.
5. Conclusion: Both scenarios lead to a total logical impossibility. The initial assumption that decider $H$ exists must be false.
   Therefore, $A_{\text{TM}}$ is fundamentally UNDECIDABLE.

---

🔗 Reductions: The Lever of Undecidability

Once Alan Turing proved that the Halting Problem is undecidable, how do computer scientists prove that other problems are undecidable? We use Reductions.

Intuition: A reduction is a mathematical lever. If you can show that solving Problem $B$ would automatically allow you to solve the Halting Problem $A_{\text{TM}}$, then because the Halting Problem is impossible, Problem $B$ must also be impossible!

Mapping Reductions (A ≤_m B)

A language $A$ is mapping reducible to language $B$ (written $A \le_m B$) if there exists a computable function $f: \Sigma^* \to \Sigma^*$ such that for every string $w$:

$w \in A \iff f(w) \in B$

The Two Golden Rules of Mapping Reductions

How reductions propagate decidability forward and undecidability backward

Direction 1 (Decidability)

A ≤_m B and B is DECIDABLE

✅

Dominant Architecture / DomainPositive Propagation

• •If B is decidable, then A is GUARANTEED to be DECIDABLE.
• •Algorithm for A: To test if w ∈ A, compute f(w), then run B's decider on f(w).
• •Directly converts a solution for B into a solution for A.

"Easy problem B solves easier problem A."

Direction 2 (Undecidability)

A ≤_m B and A is UNDECIDABLE

🚫

Dominant Architecture / DomainNegative Propagation

• •If A is undecidable, then B is GUARANTEED to be UNDECIDABLE.
• •Contrapositive of Direction 1: If B were decidable, A would be decidable, creating a contradiction!
• •The standard proof technique for establishing new undecidable problems.

"If A is impossible, then harder problem B must be impossible."

---

🌾 Rice's Theorem: The Ultimate Bulldozer of Computability

In 1951, Henry Gordon Rice generalized Turing's Halting Problem into the single most powerful theorem in computability theory.

Rice's Theorem:
ANY non-trivial semantic property of the language of a Turing Machine is UNDECIDABLE.

To apply Rice's Theorem correctly, you must master two precise definitions:

Understanding Semantic Properties

A property $P$ is a semantic property (a property of the language) if it depends purely on the set of strings the machine accepts ($L(M)$), NOT on the physical code or syntax of $M$.

• If two completely different Turing Machines $M_1$ and $M_2$ accept the exact same language ($L(M_1) = L(M_2)$), then either both satisfy property $P$, or neither satisfies property $P$:

$$L(M_1) = L(M_2) \implies (M_1 \in P \iff M_2 \in P)$$

Understanding Non-Trivial Properties

A property $P$ is non-trivial if:

1. There is at least one Turing Machine whose language has property $P$ (it is not empty).
2. There is at least one Turing Machine whose language does NOT have property $P$ (it does not include all TMs).

Instant Undecidability: 6 Problems Solved by Rice's Theorem

Common compiler questions proven undecidable in under 3 seconds using Rice's Theorem

📭

Emptiness Problem

L(M) = ∅

• Is the language of Turing Machine M empty?
• Semantic: depends on L(M).
• Non-trivial: True for M_reject, False for M_accept.
• Verdict: UNDECIDABLE via Rice's Theorem.

Key Abstractions / Calls

Test: L(M) == ∅Rice Rule: Undecidable

🔢

Finiteness Problem

|L(M)| < ∞

• Does Turing Machine M accept finitely many strings?
• Semantic: depends on language cardinality.
• Non-trivial: True for L = {0, 1}, False for L = Σ*.
• Verdict: UNDECIDABLE via Rice's Theorem.

Key Abstractions / Calls

Test: |L(M)| < ∞Rice Rule: Undecidable

⚡

Regularity Problem

L(M) is Regular?

• Is the language of Turing Machine M regular?
• Semantic: depends on language class.
• Non-trivial: True for L = 0*, False for L = aⁿ bⁿ.
• Verdict: UNDECIDABLE via Rice's Theorem.

Key Abstractions / Calls

Test: L(M) ∈ REGRice Rule: Undecidable

🎯

Specific String Membership

"hello" ∈ L(M)

• Does M accept the specific string "hello"?
• Semantic: depends purely on L(M).
• Non-trivial: True for some TMs, False for others.
• Verdict: UNDECIDABLE via Rice's Theorem.

Key Abstractions / Calls

Test: w ∈ L(M)Rice Rule: Undecidable

🌌

Universality / Totality

L(M) = Σ*

• Does M accept every possible input string?
• Semantic: checks totality of language.
• Non-trivial: True for M_accept_all, False for M_empty.
• Verdict: UNDECIDABLE via Rice's Theorem.

Key Abstractions / Calls

Test: L(M) == Σ*Rice Rule: Undecidable

🥞

Context-Freeness

L(M) is CFL?

• Can the language of M be generated by a CFG?
• Semantic: property of language family.
• Non-trivial: True for L = aⁿ bⁿ, False for aⁿ bⁿ cⁿ.
• Verdict: UNDECIDABLE via Rice's Theorem.

Key Abstractions / Calls

Test: L(M) ∈ CFLRice Rule: Undecidable

⚠️ When Does Rice's Theorem NOT Apply? (Syntactic Properties)

Rice's Theorem applies ONLY to semantic properties of the language $L(M)$. It does NOT apply to syntactic properties of the Turing Machine's source code or state table:

• "Does machine $M$ have more than 5 states?" $\implies$ DECIDABLE! (Just count the states in $Q$).
• "Does machine $M$ halt on string $w$ within 100 steps?" $\implies$ DECIDABLE! (Simulate $M$ on $w$ for 100 steps and inspect the clock).
• "Does machine $M$ contain a transition on input symbol 0?" $\implies$ DECIDABLE! (Scan the transition table).

---

🧩 The Post Correspondence Problem (PCP)

In 1946, mathematician Emil Post formulated an elegant puzzle called the Post Correspondence Problem (PCP) that does not mention Turing Machines or states, yet is fundamentally UNDECIDABLE.

The Domino Tile Match Game

You are given a finite set of $k$ domino tiles. Each domino tile has a top string and a bottom string:

$\left[ \frac{t_1}{b_1} \right], \quad \left[ \frac{t_2}{b_2} \right], \quad \dots, \quad \left[ \frac{t_k}{b_k} \right]$

The Objective: Does there exist a sequence of indices $i_1, i_2, \dots, i_m$ (with repetitions permitted) such that concatenating the top strings yields the exact same string as concatenating the bottom strings?

$\text{Match Condition}: \quad t_{i_1} t_{i_2} \cdots t_{i_m} = b_{i_1} b_{i_2} \cdots b_{i_m}$

The Post Correspondence Problem Match Condition

Finding a tile sequence where concatenated numerator equals concatenated denominator

Top String Stream

Numerator Sequence: t_{i₁} t_{i₂} ... t_{iₘ}

🀄

Concatenation of all chosen top strings from the selected domino sequence.

Tile i₁ topTile i₂ topArbitrary tile repetitions allowed

↓Must Equal String-for-String

Bottom String Stream

Denominator Sequence: b_{i₁} b_{i₂} ... b_{iₘ}

🀄

Concatenation of all chosen bottom strings from the exact same index sequence.

Tile i₁ bottomTile i₂ bottomIdentical index ordering

The PCP Undecidability Theorem

Theorem (Emil Post, 1946):
The Post Correspondence Problem is UNDECIDABLE for any alphabet with $|\Sigma| \ge 2$. There is no general algorithm that can determine whether an arbitrary set of dominoes has a match.

(Note: For a single-letter alphabet $|\Sigma| = 1$, PCP reduces to finding integer multiples and is DECIDABLE).

Why is PCP so Important?

PCP serves as the primary reduction bridge to prove that Context-Free Grammar problems are undecidable:

• By encoding valid Turing Machine computation histories into PCP domino tiles, computer scientists proved that:
  • CFG Ambiguity is UNDECIDABLE (via reduction from PCP).
  • CFG Universality ($L(G) = \Sigma^*$) is UNDECIDABLE (via reduction from PCP).
  • CFG Equivalence ($L(G_1) = L(G_2)$) is UNDECIDABLE.

---

🏭 Real-World Production Context: Antivirus Scanners & Security Auditing

Why can't cybersecurity companies build a "perfect" antivirus software that guarantees 100% detection of all zero-day malware?

Architecture Flow

The Malware Detection Undecidability Impasse

Why Rice's Theorem mathematically limits automated cybersecurity detection

💾Unknown Binary

Target Executable ⟨P⟩

Untrusted binary file submitted to enterprise antivirus scanner.

→

Static Analysis

🛡️Security Query

Does P Delete Files?

Antivirus evaluates: does execution path of P delete user files on disk?

→

Apply Rice's Theorem

🚫The Theoretical Wall

Rice's Theorem Barrier

Testing whether a program deletes files is a non-trivial semantic property: UNDECIDABLE!

→

Industry Workaround

⚡Industrial Antivirus

Signatures & Sandboxing

Antivirus relies on virus signatures (syntactic checks) and heuristics instead of general semantic proof.

Industrial Case Studies

1. Total Virus Detection is Impossible: If a perfect malware scanner is_virus(P) existed, a hacker could write:

   def spiteful_payload():
       if is_virus(spiteful_payload):
           exit(0) # Harmless: does not act as virus
       else:
           delete_operating_system() # Malicious: acts as virus!

   By Turing's diagonalization paradox, is_virus cannot exist.
2. Compiler Dead Code Elimination: Compilers want to remove functions that are never called ($L(\text{Execution}) = \emptyset$). Because Rice's Theorem proves emptiness is undecidable, compilers use conservative approximations (call graph analysis) that only prune guaranteed unreferenced code.

---

📐 Numerical Applications & Worked Examples

Problem 1: Solving a Concrete Instance of the Post Correspondence Problem

Problem Statement:
Consider the following set of 3 domino tiles over alphabet $\Sigma = \{a, b\}$:

$\text{Tile 1}: \left[ \frac{a}{a a b} \right], \quad \text{Tile 2}: \left[ \frac{b}{a} \right], \quad \text{Tile 3}: \left[ \frac{b a a}{a} \right]$

Determine whether this instance of PCP has a valid match. If yes, provide the sequence of tile indices.

Step-by-Step Solution:

Step 1: Analyze Starting Tile Candidates

The top string and bottom string must begin with the exact same character:

• Tile 1 starts with a on top and a on bottom $\implies$ Valid start candidate.
• Tile 2 starts with b on top and a on bottom $\implies$ Mismatch! Cannot start.
• Tile 3 starts with b on top and a on bottom $\implies$ Mismatch! Cannot start.
• Therefore, any valid match MUST begin with Tile 1!

Step 2: Trace Tile Sequence

• Step 1 (Pick Tile 1):
  • Top: $a$
  • Bottom: $a a b$
  • Deficit: Top needs $a b$.
• Step 2 (Pick Tile 3):
  • Top: $a + b a a = \mathbf{a b a a}$
  • Bottom: $a a b + a = \mathbf{a a b a}$
  • Deficit: Top and bottom start matching: a matches a, but second characters are b vs a! Mismatch!
• Let us reconsider the tiles:
  • Wait! Look at:
    • Tile 1: $t_1 = b, b_1 = b a$
    • Let's test sequence: $i = (2, 1, 3)$ or $(1, 2, \dots)$?
    • For Tile 1: $\text{Top} = a$, $\text{Bottom} = aab$.
    • If next tile is Tile 2: $\text{Top} = ab$, $\text{Bottom} = aaba$. Mismatch!
• Let us inspect whether a match exists:
  • Length of $t_1 = 1, b_1 = 3$. Length of $t_2 = 1, b_2 = 1$. Length of $t_3 = 3, b_3 = 1$.
  • Notice: Tile 1 adds $+2$ to bottom length. Tile 3 adds $+2$ to top length. Tile 2 has equal lengths!
  • Let us test the sequence: $i = (1, 2, 1, 3, 3)$:
    • Top: $t_1 t_2 t_1 t_3 t_3 = a \cdot b \cdot a \cdot baa \cdot baa = \mathbf{a b a b a a b a a}$ (length 9).
    • Bottom: $b_1 b_2 b_1 b_3 b_3 = aab \cdot a \cdot aab \cdot a \cdot a = \mathbf{a a b a a a b a a}$ (length 9).
    • Compare:
      • Top: a b a b a a b a a
      • Bottom: a a b a a a b a a (character 2 differs: b vs a!).
• Let us test sequence: $i = (2, 1, 1, 3)$:
  • But the sequence must start with matching initial character! Since only Tile 1 starts with a/a, it must start with Tile 1.
  • After Tile 1, top is a and bottom is aab. Top needs ab....
  • Can any top string provide ab...?
    • Tile 1 top is a.
    • Tile 2 top is b (not ab).
    • Tile 3 top is baa (not ab).
  • Since no tile top begins with ab, the top can NEVER catch up to match the bottom!

Step 3: Conclusion

Because the initial lead of ab on the bottom can never be matched by any sequence of top strings, this PCP instance has NO MATCH.

---

Problem 2: Applying Rice's Theorem to Semantic Predicates

Problem Statement:
Determine whether each of the following properties is decidable or undecidable using Rice's Theorem:

1. $P_1 = \{ \langle M \rangle \mid M \text{ accepts all palindromes over } \{0, 1\} \}$
2. $P_2 = \{ \langle M \rangle \mid M \text{ has exactly 7 states in its state set } Q \}$
3. $P_3 = \{ \langle M \rangle \mid L(M) \text{ is an empty language} \}$
4. $P_4 = \{ \langle M \rangle \mid M \text{ takes more than 100 steps on input } 001 \}$

Step-by-Step Solution:

Part 1: P₁ (Accepts all palindromes)

• Is it semantic? Yes, it depends purely on whether $\text{Palindromes} \subseteq L(M)$.
• Is it non-trivial? Yes: True for $M_{\text{accept\_all}}$ ($L = \Sigma^*$), False for $M_{\text{empty}}$ ($L = \emptyset$).
• Verdict: By Rice's Theorem, $P_1$ is UNDECIDABLE.

Part 2: P₂ (Has exactly 7 states)

• Is it semantic? NO! Two machines with different numbers of states (e.g. one with 7 states, one with 10 states) can accept the exact same language. This is a syntactic property of the machine, not a property of $L(M)$.
• Verdict: Rice's Theorem does NOT apply. $P_2$ is DECIDABLE (simply count the states in $M$'s description $\langle M \rangle$).

Part 3: P₃ (Language is empty)

• Is it semantic? Yes, $L(M) = \emptyset$.
• Is it non-trivial? Yes: True for $M_{\text{empty}}$, False for $M_{\text{accept\_all}}$.
• Verdict: By Rice's Theorem, $P_3$ is UNDECIDABLE.

Part 4: P₄ (Takes more than 100 steps on 001)

• Is it semantic? NO! Running time depends on machine implementation, not language.
• Verdict: Rice's Theorem does NOT apply. $P_4$ is DECIDABLE (simulate $M$ on $001$ for 101 steps and observe the clock).

---

Problem 3: Proving Undecidability via Mapping Reduction (A_TM ≤_m HALT_TM)

Problem Statement:
Given that $A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ accepts } w\}$ is undecidable, prove that the general Halting Problem $\text{HALT}_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ halts on } w\}$ is UNDECIDABLE by showing a mapping reduction $A_{\text{TM}} \le_m \text{HALT}_{\text{TM}}$.

Step-by-Step Solution:

Step 1: Understand the Goal

We want to construct a computable function $f(\langle M, w \rangle) = \langle M', w \rangle$ such that:

$M \text{ accepts } w \iff M' \text{ halts on } w$

Step 2: The Difference Between A_TM and HALT_TM

• In $A_{\text{TM}}$, the machine must halt and accept. If $M$ halts and rejects, it does NOT belong to $A_{\text{TM}}$.
• In $\text{HALT}_{\text{TM}}$, the machine is accepted if it halts for any reason (even if it rejects).

Step 3: Construct Machine M'

Given $\langle M, w \rangle$, define a new machine $M'$ that runs as follows:

1. When $M'$ receives input $w$, it simulates $M$ on $w$.
2. If $M$ enters an accepting state: $M'$ HALTS AND ACCEPTS.
3. If $M$ enters a rejecting state: $M'$ ENTERS AN INFINITE LOOP!

Step 4: Verify Equivalence

• If $M$ accepts $w$: $M'$ halts $\implies \langle M', w \rangle \in \text{HALT}_{\text{TM}}$.
• If $M$ does not accept $w$:
  • If $M$ rejects $w$, $M'$ loops forever $\implies M'$ does not halt.
  • If $M$ loops forever on $w$, $M'$ loops forever $\implies M'$ does not halt.
  • In both rejection cases, $\langle M', w \rangle \notin \text{HALT}_{\text{TM}}$.

Step 5: Conclusion

We have constructed a valid reduction $A_{\text{TM}} \le_m \text{HALT}_{\text{TM}}$.
Since $A_{\text{TM}}$ is undecidable, $\text{HALT}_{\text{TM}}$ must be UNDECIDABLE.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Why does Rice's Theorem apply only to semantic properties and not syntactic ones?
  Because the syntax of a program (number of lines, variable names, number of states) can be trivially inspected by reading its source text in $O(N)$ time. Rice's Theorem addresses the meaning (behavior) of the program—what strings it actually accepts—which requires running the machine into potential infinite loops.
• Is the Post Correspondence Problem decidable if $|\Sigma| = 1$?
  YES! If the alphabet has only one symbol (e.g. $\Sigma = \{a\}$), strings are completely characterized by their lengths. A tile $\left[\frac{a^p}{a^q}\right]$ is just a ratio $p/q$. Finding a match reduces to finding a linear combination $\sum x_i p_i = \sum x_i q_i \iff \sum x_i (p_i - q_i) = 0$, which is solvable via simple linear integer programming. PCP is undecidable only when $|\Sigma| \ge 2$.
• If $A \le_m B$ and $A$ is decidable, does that mean $B$ is decidable?
  NO! This is the most common student error. A reduction $A \le_m B$ means $A$ is "easier than or equal to" $B$. Knowing that an easy problem $A$ is decidable tells you nothing about whether the harder problem $B$ is decidable. (For example, regular languages reduce to the Halting Problem, but the Halting Problem is undecidable!).

Common Interview Traps

• Trap: Confusing Rice's Theorem with Rice's First Name:
  Rice's Theorem applies strictly to Turing Machines! It does NOT apply to Finite Automata or PDAs. Emptiness and Finiteness are decidable for DFAs and CFGs, but undecidable for Turing Machines.
• Trap: Assuming Rice's Theorem Applies to Syntactic Dead Code:
  Checking whether a specific function foo() has an explicit call instruction in your source file is syntactic (DECIDABLE). But checking whether foo() will ever be reached at runtime on some input is semantic (UNDECIDABLE).
• Trap: Believing PCP Requires Finite Number of Tiles to Pick From:
  PCP has a finite alphabet of tile types, but the sequence of tiles chosen can be arbitrarily long (e.g. a match might require using 1,000,000 dominoes with thousands of repetitions). Because the search tree is unbounded, brute-force search is not guaranteed to terminate.

---

🗺️View Complete DBMS Roadmap & Syllabus

← Previous Topic10.1 Recursive (REC) vs Recursively Enumerable (RE / Semi-Decidable) LanguagesNext Topic →10.3 Master Decision & Closure Properties Matrix Across All 4 Chomsky Classes