GATE CS 1987 Q2l — Turing Machines

The given statement is TRUE (represented by 1).

Explanation:

A language $A$ is recursive (decidable) if and only if both $A$ and its complement $\bar{A}$ are recursively enumerable (accepted by Turing machines).

• If $A$ is recursive: There exists a Turing machine $M$ that halts on all inputs and decides $A$. We can construct another halting Turing machine $M'$ that decides $\bar{A}$ by simply swapping the accept and reject behaviors of $M$. Since both $M$ and $M'$ halt on all inputs, they both accept $A$ and $\bar{A}$ respectively.
• If both $A$ and $\bar{A}$ are accepted by Turing machines: Let $M_1$ be the Turing machine that accepts $A$, and $M_2$ be the Turing machine that accepts $\bar{A}$. We can construct a new Turing machine $M$ to decide $A$ by running $M_1$ and $M_2$ in parallel (using step-by-step interleaving) on any input $w$:
  • Since $w$ must belong to either $A$ or $\bar{A}$, exactly one of $M_1$ or $M_2$ is guaranteed to eventually halt and accept $w$.
  • If $M_1$ accepts, $M$ halts and accepts.
  • If $M_2$ accepts, $M$ halts and rejects.
  Since $M$ is guaranteed to halt on every input, the language $A$ is recursive.