Chapter 5 · Watch, then practise
Undecidability
Distinguish recognition from guaranteed decisions and practice the direction of a reduction.
3 questions · 3 with related videos. Matches are based on playlist titles; broader background matches are labeled.
What to study
- Recognizers and deciders
- Complement languages
- Mapping reductions
- Rice’s theorem
Chapter playlists
Choose a playlist
Lec-64: Recursive vs Recursive Enumerable Languages | TOC
Gate Smashers · 6:56
Compares recursive and recursively enumerable languages, the relevant distinction between deciders and recognizers.
1. Halting matters
Why does swapping accept and reject states complement a decider but not necessarily a recognizer?
A decider halts on every input, so swapping its two outcomes decides the complement. A recognizer may loop on a nonmember. Swapping halting states leaves that loop unchanged instead of accepting it, so this construction need not recognize the complement.
9. Reducibility
MIT OpenCourseWare · 1:16:37
Supplementary MIT lecture on reducibility for reasoning about the direction of an undecidability reduction.
2. Direction of a reduction
To prove a problem B undecidable using known undecidable A, which reduction is needed?
Construct a total computable function f with x ∈ A exactly when f(x) ∈ B. If a decider for B existed, applying f and then that decider would decide A, a contradiction. Thus A ≤ₘ B transfers undecidability to B. Reversing the arrow does not establish this conclusion.
Rice Theorem for Programs - Undecidability | Theory of Computation | GO Classes | Deepak Poonia Sir
GO Classes for GATE CS · 34:18
Supplementary Rice-theorem lesson for distinguishing semantic program properties from syntactic descriptions.
3. When Rice’s theorem applies
Compare “M accepts the string 101” with “M has five states.”
Acceptance of 101 is a nontrivial property of the language recognized by M, so Rice’s theorem makes it undecidable from arbitrary TM descriptions. Having five states concerns the description’s structure and can be checked directly. Rice’s theorem concerns language properties, not every question about a machine.