Consider the following problem X “Given a Turing Machine M over the input…

PYQ GATE 2001

Consider the following problem X

“Given a Turing Machine M over the input alphabet Σ any state q of M and word Σ*, does the computation of M on w visit the state q”

Which of the following X is correct?

  1. A.

    X is undecidable but partially decidable

  2. B.

    X is not a decision problem

  3. C.

    X is decidable

  4. D.

    X is undecidable but not even partially decidable

Attempted by 260 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…