Solution

The correct answer is B and D only

Key Points

• A. The set of Turing machine codes for TMs that accept all inputs that are palindromes is decidable:
  • A Turing machine accepts an input it if halts in an accept state. To say that a TM accepts all inputs that are palindromes means that every palindrome string needs to be an accepted input.
  • This essentially needs us to determine the behavior of a Turing machine, which is generally undecidable due to the halting problem. The halting problem is a famous problem in computation which implies that there is no way to know with certainty whether a Turing machine will halt or continue forever.
  • Therefore, a set of Turing Machine codes that accept palindromes is not 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:
  • This is a form of the halting problem, because in order to know if a Turing machine will eventually write '1' on the tape means we are asked to determine if a Turing machine will halt (write '1' and stop) or not. As we discussed earlier with point A, the halting problem is known to be undecidable.
• C. The language accepted by a TM M is L(M) is always recursive:
  • It's true that Turing machines recognize recursively enumerable languages, but it's not true that all languages a TM recognizes are recursive.
  • A recursive language (also called a decidable language) is one where a TM will always halt with a 'yes' or 'no' answer - i.e., it will always accept or reject.
  • However, there are languages where the TM might not halt for some strings — these are the recursively enumerable (r.e.) but not recursive languages. For this reason, statement C is false.
• D. Post's correspondence problem is undecidable:
  • Post's Correspondence Problem (PCP) is known to be undecidable, which means there is no algorithm that exists that can solve all instances of the PCP.
  • Introduced by Emil Post in 1946 as a way of demonstrating that there were problems that were even impossible for a Turing Machine to solve, it serves as a classic example of the limits of computation.

So, the Option 4) B and D only remains the correct answer.