Undecidable Problems in Computer Science

Why This Matters

Understanding undecidable problems isn't just about memorizing a list of unsolvable puzzles—it's about grasping the fundamental limits of computation itself. These problems reveal that no matter how powerful our computers become, certain questions will always be beyond algorithmic reach. You're being tested on your ability to recognize why specific problems are undecidable, how they relate to Turing machines, and what techniques (like reduction and diagonalization) prove their undecidability.

These concepts connect directly to the Church-Turing thesis, the hierarchy of computational complexity, and the theoretical foundations that underpin everything from compiler design to artificial intelligence. When you encounter these problems on an exam, don't just recall their names—know what category of undecidability they represent and how they demonstrate the boundary between what machines can and cannot do.

---

Problems Proven by Diagonalization

The diagonalization technique, pioneered by Turing, constructs a contradiction by assuming an algorithm exists and then building an input that breaks it. This self-referential approach reveals problems where programs must reason about their own behavior.

The Halting Problem

• No algorithm can determine whether an arbitrary program halts or runs forever—this is the foundational undecidable problem in computer science
• Alan Turing proved this in 1936 using diagonalization, showing that a hypothetical "halt-checker" leads to logical contradiction
• Establishes the decidable/undecidable boundary and serves as the basis for proving other problems undecidable through reduction

The Entscheidungsproblem (Decision Problem)

• Asks whether any algorithm can determine the truth of all mathematical statements—answered negatively by Turing and Church in the 1930s
• Church used lambda calculus while Turing used his machine model, both arriving at the same conclusion independently
• Historically pivotal for establishing that formal systems have inherent limitations, connecting to Gödel's incompleteness theorems

---

Problems About Program Properties

Rice's Theorem provides a sweeping result: any non-trivial semantic property of programs is undecidable. These problems ask questions about what programs do rather than how they're written.

Rice's Theorem

• All non-trivial properties of Turing-recognizable languages are undecidable—if a property isn't true for all programs or false for all programs, you can't algorithmically detect it
• Provides a general framework for instantly classifying many problems as undecidable without individual proofs
• "Non-trivial" is key—the property must distinguish between at least two programs, not just examine syntax

The Universality Problem

• Asks whether a given Turing machine accepts all possible inputs—proven undecidable by reduction from the Halting Problem
• Directly tests language properties, making it a textbook application of Rice's Theorem
• Connects to the Church-Turing thesis by examining what it means for a machine to be computationally complete

The Equivalence Problem for Context-Free Grammars

• Determining if two CFGs generate the same language is undecidable—even though membership testing for CFGs is decidable
• Illustrates hierarchy of decidability within formal language theory; some grammar questions are answerable, others aren't
• Critical for compiler theory, showing why automated grammar comparison tools have fundamental limitations

---

Problems Involving Combinatorial Search

Some undecidable problems arise from seemingly simple matching or tiling tasks where no algorithm can exhaustively verify all possibilities. These connect computation to geometry, algebra, and formal languages.

Post's Correspondence Problem

• Given pairs of strings, no algorithm can determine if a matching sequence exists—where concatenating top strings equals concatenating bottom strings
• Introduced by Emil Post in 1946 as a simpler alternative to the Halting Problem for proving undecidability
• Frequently used in reductions to prove other problems undecidable, especially in formal language theory

The Tiling Problem

• No algorithm can determine if a given tile set can cover an infinite plane—without gaps or overlaps, using only translation (no rotation)
• Hao Wang conjectured it was decidable in the 1960s, but his student Robert Berger proved otherwise
• Connects to aperiodic tilings like Penrose tiles, bridging computation, geometry, and crystallography

---

Problems in Algebra and Number Theory

Undecidability isn't confined to computer science—it reaches into pure mathematics, showing that certain algebraic and number-theoretic questions have no algorithmic solution.

Hilbert's Tenth Problem

• No algorithm can determine if a Diophantine equation has integer solutions—proven by Yuri Matiyasevich in 1970, completing work by Davis, Putnam, and Robinson
• Originally posed by David Hilbert in 1900 as part of his famous 23 problems for 20th-century mathematics
• Bridges number theory and computability, showing that polynomial equations encode undecidable computational problems

The Word Problem for Groups

• For certain groups, no algorithm can determine if two symbolic expressions represent the same element—undecidability proven for finitely presented groups
• First posed by Max Dehn in 1911, decades before computability theory existed
• Has implications for topology since fundamental groups of manifolds can have undecidable word problems

---

Problems About Computational Growth

Some problems are undecidable because they require computing functions that grow faster than any computable function. These reveal the extreme limits of algorithmic reasoning.

The Busy Beaver Problem

• Finding the maximum steps a halting $n$-state Turing machine takes is non-computable—the Busy Beaver function $BB(n)$ grows faster than any computable function
• Not just "very hard" but provably impossible—if you could compute $BB(n)$, you could solve the Halting Problem
• Demonstrates uncomputability through growth rates, showing some well-defined mathematical functions simply cannot be calculated

---

Quick Reference Table

---

Self-Check Questions

1. Which two problems both rely on self-reference and diagonalization, and what distinguishes their domains?

2. If you needed to prove a new problem about Turing machine behavior is undecidable, which theorem would give you the fastest path—and what condition must the property satisfy?

3. Compare Post's Correspondence Problem and the Tiling Problem: what structural similarity makes both undecidable, and how do their dimensions differ?

4. Why is the Busy Beaver function non-computable rather than merely difficult to compute? What would be the consequence if we could compute it?

5. An FRQ asks you to explain why determining if a program ever outputs "hello" is undecidable. Which theorem directly applies, and what would your one-sentence justification be?