For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages. L 1 = {(M) | M takes more than 2021 steps on all inputs} L 2 = {(M) | M takes more than 2021 steps on some input} Which one of the following options is correct?

Correct Answer is : Both L1 and L2 are decidable.

Both L 1 and L 2 are undecidable.

L 1 is undecidable and L 2 is decidable.

L 1 is decidable and L 2 is undecidable.

Both L 1 and L 2 are decidable.

GATE Computer Science (CS) 2021 Shift 1 Solved Paper

Question : 49 of 65

Marks: +1, -0

For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages.
L₁ = {(M) | M takes more than 2021 steps on all inputs}
L₂ = {(M) | M takes more than 2021 steps on some input}
Which one of the following options is correct?

Both L₁ and L₂ are undecidable.
L₁ is undecidable and L₂ is decidable.
L₁ is decidable and L₂ is undecidable.
Both L₁ and L₂ are decidable.

Validate

Go to Question:

Prev Question

Next Question