A. The set of turning machine codes for TM's that accept all inputs that are palindromes (possible along with some other inputs) is decidable

B. The language of codes for TM's M that when started with blank tape, eventually write a 1 somewhere on the tape is undecidable

C. The language accepted by a TMM is LM is always recursive

D. Post's correspondence problem is undecidable

1. AA, B and C only
2. BB, C and D only
3. CA and C only
4. DB and D only G = R H = {−1, 1}

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: D. B and D only G = R H = {−1, 1}

Explanation

By Rice's theorem, 'accepts all palindromes' is a non-trivial language property, so A is undecidable (false). Writing a 1 on a blank tape is undecidable (B true). A TM's language is recursively enumerable, not always recursive (C false). PCP is undecidable (D true).