• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Theory of Computation

Let a decision problem X be defined as follows: X: Given a Turing machine M over the input alphabet {0, 1} and any word w in {0, 1}*, does M loop forever on w? You may assume that the halting problem for Turing machines is undecidable but partially decidable. A. Show that X is undecidable. B. Show that X is not even partially decidable.

GATE 2001 · Theory of Computation · Decidability · easy

Answer: X is undecidable (Part A) and not even partially decidable (Part B), because X = co-HALT and the complement of a non-recursive RE language is not RE.

  1. Part A: X is undecidable: Assume X is decidable. Then given (M, w), we can decide whether M loops forever on w. But 'M halts on w' = NOT 'M loops forever on w'. So we could also decide HALT by running the decider for X and flipping the output. This contradicts the assumed undecidability of HALT. Therefore X is undecidable.
  2. Part B: X is not partially decidable: We know HALT is partially decidable (RE). If X = co-HALT were also partially decidable (RE), then by the theorem 'if L and complement(L) are both RE, then L is recursive', HALT would be decidable. But HALT is undecidable — contradiction. Therefore X = co-HALT cannot be RE, i.e., X is not partially decidable.