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.17K 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. In which principle, the models created explain the identification of a problem and find its solution?

Q. This clustering algorithm terminates when mean values computed for the current iteration of the algorithm are identical to the computed mean values for the previous iteration

Q. Message ________ means privacy that the sender and reciever expect privacy.

Q. Decision Tree is

Q. Which of the following term is best defined by the statement: “Derive traceability information to maximize information hiding in the design.”?

Q. In the alert protocol the first byte takes the value 1 or 2 which corresponds to _________ and _________ respectively.

Q. What are the methods in which use case descriptions can be written?

Q. …………..defines the structure of a relation which consists of a fixed set of attribute-domain pairs.

Q. The Use case Description Heuristics includes which of these?

Q. The right level of parallelism for maps seems to be around maps per- node.