Lecture on Decidability and Undecidability Problems

Introduction

• Recording for later review due to potential stream issues.
• Overview of decidable problems: acceptance and emptiness problems for context-free grammars (CFGs).
• Focus on undecidable problems: equality for CFGs, equality for Turing machines, and emptiness for Turing machines.

The ATM Problem

• ATM Problem: Acceptance problem for Turing machines.
• Similar to ADFA (deterministic finite automata) and ACFG problems, but uses Turing machines.
• Claim: ATM is undecidable.
  • No algorithm to decide ATM, but it is recognizable.
• Recognition: If a Turing machine M accepts a string W, then accept.
• Undecidability Proof:
  • Use proof by contradiction.
  • Assume ATM is decidable and derive a contradiction.
  • Construct a contradictory machine D using a hypothetical decider H for ATM.
  • D performs the opposite of H; leads to contradictions when D runs on itself.
  • Conclude that ATM is undecidable.

Theorem: L is Decidable if and only if L and L-bar are Recognizable

• If both a language and its complement are recognizable, the language is decidable.
• Forward direction: If L is decidable, it is recognizable; L-bar is also recognizable.
• Backward direction: Suppose A recognizes L, and B recognizes L-bar.
  • Simulate both machines; decide based on which accepts.
• Consequence: ATM-bar is not recognizable because ATM is not decidable.

Visual Representation

• Hierarchy of languages:
  • Regular, CFLs, Decidable, Recognizable, and Non-recognizable.
  • Position of ATM and ATM-bar in the hierarchy.

Emptiness Problem for Turing Machines (ETM)

• ETM: Check if the language of a Turing machine is empty.
• Claim: ETM is undecidable.
  • Use proof by contradiction; assume ETM is decidable and solve ATM.

Equivalence Problem for Turing Machines (EQTM)

• EQTM: Check if two Turing machines have the same language.
• Claim: EQTM is undecidable.
  • Use proof by contradiction; assume EQTM is decidable and solve ETM.

Introduction to Rice's Theorem

• Rice's Theorem: Every non-trivial property of Turing machine languages is undecidable.
• Non-trivial Property: Includes at least one Turing machine and excludes at least one.
• Proof Strategy:
  • Use a proof by contradiction to show the property is undecidable.

Example Application: 3TM

• 3TM: Set of Turing machines with exactly three strings in their language.
• Use Rice's Theorem to prove it is undecidable.

Linear Bounded Automaton (LBA)

• Similar to Turing machines but with a bounded tape length.
• Acceptance Problem for LBAs: Decidable.
  • Finite number of configurations leads to a decision.

Emptiness Problem for LBAs (ELBA)

• ELBA: Check if the language of an LBA is empty.
• Claim: ELBA is undecidable.
  • Use proof by contradiction; simulate a computation history, show non-trivial property.

AllCFG Problem

• AllCFG: Check if a CFG generates all strings (sigma*).
• Claim: AllCFG is undecidable.
  • Use reversed computation histories and CFG properties.*

Equivalence Problem for CFGs (EQCFG)

• EQCFG: Check if two CFGs have the same language.
• Claim: EQCFG is undecidable.
  • Use all problem results to derive undecidability.

Summary of Decidability Results

• Categories: DFA, CFG/PDA, LBA, Turing machines.
• Problems: Acceptance, emptiness, equivalence, all-problem.
• Results: Various combinations of decidable and undecidable.

Conclusion

• Comprehensive summary of decidability and undecidability across different computational models.
• Open questions remain in computational complexity and language theory.