GATE CS 1987 Q2m — Turing Machines

The given statement is TRUE (represented as 1).

Explanation:

The problem of determining whether a given Turing machine $M$ accepts a specific input string $w$ is known as the Acceptance Problem for Turing machines, denoted as:

This problem is a classic example of an undecidable problem:

1. Recursively Enumerable (Turing-Recognizable): $A_{TM}$ is semi-decidable because we can construct a Universal Turing Machine $U$ that simulates $M$ on $w$. If $M$ accepts $w$, $U$ will eventually halt and accept. However, if $M$ loops infinitely on $w$, $U$ will also loop infinitely.
2. Not Decidable (Not Recursive): If there existed a decider $H$ that could always halt and correctly answer whether $M$ accepts $w$, we could solve the Halting Problem. By Turing's diagonalization argument, no such decider can exist.

Since no algorithm can decide $A_{TM}$ for all inputs, the problem is undecidable. Thus, the statement is TRUE.