Question 10075 – Theory-of-Computation
December 6, 2023Question 9960 – Theory-of-Computation
December 6, 2023Question 10076 – Theory-of-Computation
Which one of the following is not decidable?
Correct Answer: B
Question 22 Explanation:
(A) It is not halting problem. In halting problem number of steps can go upto infinity and that is the only reason why it becomes undecidable.
In (A) the number of steps is restricted to a finite number ‘k’ and simulating a TM for ‘k’ steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM’s is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
In (A) the number of steps is restricted to a finite number ‘k’ and simulating a TM for ‘k’ steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM’s is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps
Equivalence of two given Turing machines
Language accepted by a given finite state machine is not empty
Language generated by a context free grammar is non empty
Subscribe
Login
0 Comments