I'm going through Jeffrey D. Ullman's Introduction to Automata Theory, Languages, and Computations. The author reduces an instance of the membership problem in $L_d$ (diagonalization language) to a membership problem in $L_u$. Those are defined as follow:

$L_d = \{\langle M\rangle \mid \langle M\rangle \notin L(M)\}$

$L_u = \{\langle M, u\rangle \mid u \in L(M)\}$

We start off with assuming $L_u$ is recursive, reduce the problem in $L_d$ to a problem in $L_u$, and solve $L_d$ using the assumption that $L_u$ is recursive, now since $L_d$ is not even recursively enumerable, our assumption that $L_u$ is recursive turns out to be wrong, and since $L_u$ has a TM which accepts it, we conclude $L_u$ is a RE but not recursive language. A few pages later, the books says:

Theorem 9.7: If there is a reduction from $P_1$ to $P_2$ then

a) If $P_1$ is undecidable then so is $P_2$

b) If $P_1$ is non RE then so is $P_2$

I'm confused about the part b) of this theorem, it says reducing a non RE problem to another problem gives you a non RE problem, but having reduced an instance of $L_d$ to an instance of $L_u$, we have reduced a non RE problem to a RE but not recursive problem.


If you look closely at the proof to show that $L_u$ is not recursive, the autor is using a reduction to $\overline{L_u}$ (which is not RE), not to $L_u$, and explain that a reduction to $L_u$ cannot work since $L_u$ is RE.

  • $\begingroup$ Thank you for your answer and for helping with the formatting. My professor reduced the problem to $L_u$, I cannot see the problem with doing that, given that we are starting off with the assumption $L_u$ is recursive, it does not matter if we reduce to the complement or to $L_u$ itself, since both would be recursive, the only change we would have is, in the diagram Ullman has constructed, we would have hypothetical algorithm M for $L_u$, and if the hypothetical algorithm accepts, our machine for $L_d$ will reject, and vice-versa. $\endgroup$
    – Yueor
    May 19 '21 at 9: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.