Consider the following languages.L1 = { | M takes at least 2016 steps on some input},L2 = { | M takes at least 2016 steps on all inputs} andL3 = { | M accepts ϵ},Where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE?

Question

Examsnet · Accepted Answer

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

GATE Computer Science (CS) 2016 Shift 2 Solved Paper