Let a decision problem X be defined as follows: X: Given a Turing machine M…

PYQ GATE 2001

Let a decision problem X be defined as follows: X: Given a Turing machine M over Σ and nay word w ∈ Σ, does M loop forever on w? You may assume that the halting problem of Turing machine is undecidable but partially decidable.

(a) Show that X is undecidable.

(b) Show that X is not even partially decidable.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…