0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ I was wrong. $L_{diag}^C$ is RE. But we still have $L_{diag}\leq_RL_{diag}^C$ $\endgroup$ – Upc Jan 30 '19 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.