4.2 More Undecidability Problems
Similar to NP-Complete and NP-Hard problems.
First of all we need to find a problems that is not RE or Recursive.
Then, we reduce to another problem , such that the decider or recognizer of could decide or recognize .
(P_2) should also be non-RE or non-Recursive.
Some Additional Languages
is recursively enumerable but not recursive. is not even recursively enumerable.