October 6, 2023
October 6, 2023
October 6, 2023
###### Theory-of-Computation
October 6, 2023
 Question 2
Which of the following is/are undecidable?
 A Given two Turing machines M1 and M2, decide if L(M1)=L(M2). B Given a Turing machine M, decide if L(M) is regular. C Given a Turing machine M, decide if M accepts all strings. D Given a Turing machine M, decide if M takes more than 1073 steps on every string.
Question 2 Explanation:
Equality problem of recursively enumerable languages is undecidable, so whether two Turing machines accept the same language is undecidable.
Checking whether a Turing machine accepts a regular language is also undecidable.
Completeness problem for recursively enumerable language is undecidable thus whether a Turing Machine accepts all strings is undecidable.
Whether a Turing machine takes more than 1073 steps is decidable as we need to run the Turing Machine only for 1073 steps so no chance of going into an infinite loop hence it is decidable.
Question 2 Explanation:
Equality problem of recursively enumerable languages is undecidable, so whether two Turing machines accept the same language is undecidable.
Checking whether a Turing machine accepts a regular language is also undecidable.
Completeness problem for recursively enumerable language is undecidable thus whether a Turing Machine accepts all strings is undecidable.
Whether a Turing machine takes more than 1073 steps is decidable as we need to run the Turing Machine only for 1073 steps so no chance of going into an infinite loop hence it is decidable.