Consider the following statements:
A. The set of Turing machine codes for TMs that accept all inputs that are palindromes (possibly along with other inputs) is decidable.
B. The language of codes for TMs M that, when started with blank tape, eventually write a 1 somewhere on the tape is undecidable.
C. The language accepted by a TM M, L(M), is always recursive.
D. Post's correspondence problem is undecidable.
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. B and D only
Explanation
A is a non-trivial property of RE languages, so it is undecidable by Rice's theorem (A false). B is undecidable (true). L(M) is RE but not always recursive (C false). PCP is undecidable (D true).More Theory of Computation and Compilers questions
- Which of the following parsers is the most powerful?
- Which of the following statements is correct?
- A compiler for a high-level language that runs on one machine and produces code for another machine is called a
- Shift-reduce conflicts are resolved by:
- Match List I with List IIList I List II A. A → aB | a (a ∈ T; A, B ∈ V) I. Recursive Descent Parser B. A → BC | a (a ∈ T; A, B, C ∈ V) II.…
- Which of the following is a function of the semantic analysis phase of compilation?