GATE CS Turing Machines questions

Which one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L \subseteq\{0,1\}^{*}$

Which of the following is/are undecidable?

Consider the following languages. $L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$, $L_{2} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on all inputs} \right\}$ and $L_{3} = \left\{\left\langle M \right\rangle \mid M \ \text{accepts }\epsilon\right\}$, where …

For any two languages $L_{1}$ and $L_{2}$ such that $L_{1}$ is context-free and $L_{2}$ is recursively enumerable but not recursive, which of the following is/are necessarily true? $\bar{L}_{1}$ ( Complement of $L_{1}$) is recursive $\bar{L}_{2}$ ( Complement of $L_{2}$) is recursive $\bar{L}_{1}$ is context-free $\bar{L}_{1}$ ∪ $L_{2}$ …

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

Recursive languages are:

State whether the following statements are TRUE or FALSE: The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.

State whether the following statement are TRUE or FALSE. $A$ is recursive if both $A$ and its complement are accepted by Turing machines.