Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?

Home / Engineering / Theory of Computation / Question

Mr. Dubey • 51.43K Points
Coach

Q.) Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?

(A) X is decidable

(B) X is undecidable but partially decidable

(D) X is not a decision problem

Correct answer : Option (A) - X is decidable

Discusssion

Related MCQs on Theory of Computation

Q. Proof Carrying Code ...............

Q. The situation wherein the data of operands are not available is called ______

Q. How do Storage administrators ensure secure access to storage devices?

Q. Which of the following quantities are minimized directly or indirectly during parameter estimation in Gaussian distribution Model?

Q. Devices and other systems ________

Q. Let K be a group with 8 elements. Let H be a subgroup of K and H<K. It is known that the size of H is at least 3. The size of H is

Q. In Data reduction

Q. A CUDA program is comprised of two primary components: a host and a _____.

Q. Consider the set A={{1,3,5},{7,9,11},{13,15}} then determine which of the following is/are true. 1.1ЄA 2.{{1,3,5}} CA 3. Ф subet of A 4. A

Q. In web mining, _________ is used to know which URLs tend to be requested together.