GATE CS 2021 Set 1 Q.49 (CS Q.39): Decidability, Reducibility and Undecidability

For a Turing machine $M$ , $\langle M \rangle$ denotes an encoding of $M$ . Consider the following two languages.

L_1 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on all inputs}\}

L_2 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on some input}\}

Which one of the following options is correct?

Both $L_1$ and $L_2$ are decidable.

$L_1$ is decidable and $L_2$ is undecidable.

$L_1$ is undecidable and $L_2$ is decidable.

Both $L_1$ and $L_2$ are undecidable.

Official answer and solution

Official answer: A
From: Official GATE 2021 answer key

Solution

Observe that within a fixed bound of 2021 steps, a Turing machine can only access at most 2021 tape cells, rendering both properties finite and decidable.

In 2021 computation steps, a deterministic Turing machine $M$ can move its read/write head at most 2021 positions to the right from the starting cell. Therefore, the machine cannot inspect any symbol beyond the first 2021 cells of the input tape.

Because the input alphabet $\Sigma$ is finite, there are at most $|\Sigma|^0 + |\Sigma|^1 + \dots + |\Sigma|^{2021}$ distinct input prefixes of length up to 2021. Any two inputs with the same prefix of length 2021 yield identical head trajectories and step counts up to step 2021.

For language $L_1$ : Simulate $M$ on each of the finitely many input prefixes for at most 2022 steps. If $M$ takes more than 2021 steps on every one of these prefixes, accept; otherwise, reject. This simulation always terminates, so $L_1$ is decidable.

For language $L_2$ : Simulate $M$ on each of the finitely many input prefixes for at most 2022 steps. If there exists at least one prefix on which $M$ runs for more than 2021 steps, accept; otherwise, reject. This simulation always terminates, so $L_2$ is also decidable.

Therefore, both $L_1$ and $L_2$ are decidable (option A).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 49 of 65, printed as CS Q.39
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source