# Can a non-RE language be reduced to an RE language?

Let $$L$$ be recursively enumerable and $$U$$ be non-recursively-enumerable. Is it possible to reduce $$U$$ to $$L$$ recursively, $$U\leq_R L$$? Personally, I do not think this is possible. If we can reduce $$U$$ to $$L$$ by a Turing machine that always halt and we also have an Turing machine that compute $$L$$ (may not halt), then we connect these two parts, we will have a Turing machine to compute $$U$$. Then $$U$$ is also recursively enumerable.

I was asked to show some language $$L$$ is recursively enumerable first, which was OK. But afterwards, I was asked to show some language which is known not recursively-enumerable, $$L_{diag}=\{w_i|M_i\text{ does not accept } w_i\}$$ can be reduced to it. I.e. $$L_{diag}\leq_R L$$ which does not make sense to me.

As you say, no non-RE language $$U$$ can be reduced to any RE language $$L$$, because, then, we could recognize $$U$$ using the reduction and the recognition algorithm for $$L$$.
The language $$L_{diag}$$ that you mention is indeed non-RE: it's the complement of an RE set that isn't recursive. There is no recursive reduction from $$L_{diag}$$ to $$L$$.
• I was wrong. $L_{diag}^C$ is RE. But we still have $L_{diag}\leq_RL_{diag}^C$ – Upc Jan 30 '19 at 16:34