CODEWITHSUNDEEP
computation-theoryturing-machinescomputability
bmzhao
bmzhao

Reputation: 41

Are there any Recursively Enumerable problems that are not RE-hard?

The computability class that I'm taking explains several languages that are in RE - REC (recursively enumerable but not recursive, i.e. solvable by a non-halting turing machine). It first shows how one of them (L_d, language of turing machines which don't accept their own encoding) is not in RE, and proves that its complement is in RE - REC. It then proves that it is reducible to the universal language (L_u, the set of all binary encodings of turing machines concatenated with a string that it accepts). It then goes on to show how L_u is RE-Hard, then reduces it to L_PCP (Post's Correspondence Problem) and then reduces that to Context Free Grammar Ambiguity. Are there any problems that are in RE, but not RE-Hard? Because so far, for every problem our professor has explained in RE - REC, he has proven they are reducible to eachother.

Upvotes: 4

Views: 796

Answers (2)

Andrea Asperti
Andrea Asperti

Reputation: 1003

The problem you mention (with the clarification of Peter Leupold, that should be integrated in the question) is known as Post problem. The answer is positive: in particular, all so called "simple" sets are RE-sets that are not many-one complete.

A simple set is a RE-set whose complementary is "immune". An immune set is a set that does not contain any infinite RE-set. This is enough to prove that a simple set cannot be complete, since the complementary of a complete set is productive, and any productive set contains an infinite RE-subset, generated by its own production function.

A few simple sets are known. My favourite example is the set of non-random numbers, according to Kolmogorov complexity, that is the set of all numbers that can be more compactly expressed as the index of a program generating it (on input 0). The proof that such a set is simple is not difficult and can be found in any good text on computability.

Upvotes: 2

Peter Leupold
Peter Leupold

Reputation: 1212

The answer to your question is yes, because even finite languages are RE. But they are by no means hard in the sense you mean.

Maybe your question is really "Are there any Recursively Enumerable problems that are not RE-hard but not recursive?" Here the answer depends on your notion of reduction. Probably your professor is using many-one reductions; then the answer is probably, YES (I am not completely sure). For weaker reductions the answer is NO.

Upvotes: 0

Related Questions