# 4.2 More Undecidability Problems

## How to?

Similar to NP-Complete and NP-Hard problems.

First of all we need to find a problems $P_1$ that is not RE or Recursive.

Then, we reduce $P_1$ to another problem $P_2$, such that the decider or recognizer of $P_2$ could decide or recognize $P_1$.

(P_2) should also be non-RE or non-Recursive.

$L_{ne}$ is recursively enumerable but not recursive. $L_e$ is not even recursively enumerable.