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 freeLoading lesson…

