Suppose that the language $L_1$ reduces to the language $L_2$ in polynomial time, $L_1\leq_p L_2$. If $L_2$ is recursive enumerable then so is $L_1$, but why isn't $L_1$ recursive? Because $L_2$ is at least as hard as $L_1$, and so $L_1$ could be easier than $L_2$. Why isn't $L_1$ recursive? Explain with an example.
1 Answer
$\begingroup$
$\endgroup$
Every language reduces to itself. Take $L_1 = L_2$ to be any recursively enumerable language which isn't recursive.