Theory-of-Computation
October 6, 2023Theory-of-Computation
October 6, 2023Theory-of-Computation
| Question 13 |
Which of the following is/are undecidable?
| Given two Turing machines M1 and M2, decide if L(M1)=L(M2). | |
| Given a Turing machine M, decide if L(M) is regular. | |
| Given a Turing machine M, decide if M accepts all strings. | |
| Given a Turing machine M, decide if M takes more than 1073 steps on every string. |
Question 13 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.
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.
Correct Answer: C
Question 13 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.
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.
Subscribe
Login
0 Comments