Skip to content

4.2 More Undecidability Problems

How to?

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.