Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Consider the following statements:
A. The set of Turing 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:
Solution
A is false because checking whether a TM accepts all palindromes is an undecidable property.
B is true because checking whether a TM writes 1 on a blank tape is undecidable.
C is false because the language accepted by a TM is recursively enumerable, but not always recursive.
D is true because Post's correspondence problem is undecidable.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
