Q61.Marks: +2.0UGC NET Paper 2: Computer Science17th June 2023
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 TM M is L (M) is always recursive
D. Post's correspondence problem is undecidable
Choose the correct answer from the options given below:
1.A, B and C only
2.B, C and D only
3.A and C only
4.B and D only✓ Correct
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.
