Which problems are decidable?
Each problem is a language of encoded inputs, as in Sipser. Theorem numbers are from the 3rd edition.
| Language | Question | Status | Sipser | Try it |
|---|---|---|---|---|
| ADFA, ANFA | Does the automaton accept w? | decidable | Theorems 4.1, 4.2 | Finite automata → Test |
| AREX | Does the regular expression generate w? | decidable | Theorem 4.3 | Regular expressions |
| EDFA | Is L(A) empty? | decidable | Theorem 4.4 | Below |
| EQDFA | Is L(A) = L(B)? | decidable | Theorem 4.5 | Below |
| ACFG | Does the grammar generate w? | decidable | Theorems 4.7, 7.16 | Grammars → CYK |
| ECFG | Is L(G) empty? | decidable | Theorem 4.8 | Below |
| EQCFG, ALLCFG | Are two grammars equivalent? Does G generate every string? | undecidable | Theorem 5.13, Exercise 5.1 | |
| ATM | Does the Turing machine accept w? | recognizable, not decidable | Theorem 4.11 | Undecidability tab |
| ATM | Does M fail to accept w? | not recognizable | Corollary 4.23 | |
| HALTTM | Does M halt on w? | recognizable, not decidable | Theorem 5.1 | Turing machines (step limit) |
| ETM, REGULARTM | Is L(M) empty? Is it regular? | undecidable | Theorems 5.2, 5.3 | |
| EQTM | Do two TMs recognize the same language? | neither recognizable nor co-recognizable | Theorems 5.4, 5.30 | |
| PCP | Does a set of dominoes have a match? | recognizable, not decidable | Theorem 5.15 | Post Correspondence tab |
A language is decidable exactly when it and its complement are both Turing-recognizable (Theorem 4.22).
Automata A and B
One move per line: from symbol to. Use commas for several symbols and ε for an empty move.
EDFA = {⟨A⟩ | L(A) = ∅}
The decider marks the start state, then keeps marking any state with an arrow coming in from a marked state. A accepts some string exactly when an accepting state gets marked (Theorem 4.4).
EQDFA = {⟨A, B⟩ | L(A) = L(B)}
The decider builds C that accepts the strings where A and B disagree, and runs the EDFA decider on C (Theorem 4.5).
ECFG = {⟨G⟩ | L(G) = ∅}
The decider marks every terminal, then marks a variable A whenever some rule A → U1⋯Uk has every Ui marked. L(G) is empty exactly when the start variable is never marked (Theorem 4.8).
The diagonal method
Cantor's argument that the real numbers cannot be listed (Theorem 4.17).
ATM is undecidable
The proof of Theorem 4.11, with the tables of Figures 4.19–4.21.
The entries are made up: the argument works no matter what the table holds.
The Post Correspondence Problem
A match is a sequence of dominoes, repeats allowed, whose top row and bottom row spell the same string. Deciding whether a set of dominoes has a match is undecidable (Theorem 5.15), so this puzzle has no general algorithm. Try it by hand, then let the computer search.
Your dominoes
One domino per line: top / bottom.
Why a search cannot always decide
A program can try sequences of 1, 2, 3, … dominoes and stop when it finds a match, so PCP is Turing-recognizable. But when there is no match the search may never end, and Sipser shows (by reducing ATM to PCP) that no program can always tell the two cases apart.
The search here stops after 14 dominoes. If it finds nothing and still has ways to continue, it says so rather than guessing.