Search code examples
computation

Language classification (computation)

I need to determine if L:={<M>|HP<=L(M)} is a recursive language, and if L is a recursively enumerable language.

I think that Rice's theorem can help prove L is not recursive but I don't think that L is recursively enumerable...

Solution

  • If L is not in RE then L is not in R either.

    You should try to reduce it to the halt problem. Lets say that X is a Turing machine that outputs false if L(X) is true and outputs true if L(X) is false.

    Is L(X) true? It is if and only if L(X) is false, which is a contradiction.

    Is L(X) false? It is if and only if L(X) is true, which is a contradiction too.

    The contradiction is in the implicit assumption that L is computable by a Turing machine. Hence L is not computable. The X Turing machine can't exist. And Finally L is not in RE (and neither in R).