Consider the following languages. L 1 = { <M> | M takes at least 2016 steps on some input}, L 2 = { <M> | M takes at least 2016 steps on all inputs} and L 3 = { <M> | M accepts ϵ}, Where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE?

Correct Answer is : L1, L2 are recursive and L3 is not recursive

L 1 is recursive and L 2 , L 3 are not recursive

L 2 is recursive and L 1 , L 3 are not recursive

L 1 , L 2 are recursive and L 3 is not recursive

GATE Computer Science (CS) 2016 Shift 2 Solved Paper

Question : 54 of 65

Marks: +1, -0

Consider the following languages.
L₁ = { <M> | M takes at least 2016 steps on some input},
L₂ = { <M> | M takes at least 2016 steps on all inputs} and
L₃ = { <M> | M accepts ϵ},
Where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE?

L₁ is recursive and L₂, L₃ are not recursive
L₂ is recursive and L₁, L₃ are not recursive
L₁, L₂ are recursive and L₃ is not recursive
L₁, L₂, L₃ are recursive

Validate

Go to Question:

Prev Question

Next Question