0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\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
    Commented May 19, 2021 at 9:34
0
$\begingroup$

$L_d$ is general reducible to $L_u$ but not map reducible to $L_u$. To show a language is not decidable, use general reduction is good enough. To show a language is RE or non-RE, you need to apply map reduction. In general reduction, $A\leq \bar{A}, A\leq B \Rightarrow A\leq \bar{B}, etc.$ However, in map reduction, $A\leq_m B \Rightarrow \bar{A}\leq_m \bar{B}$ only. In Jeffrey's book, the above two reductions are not clearly distinguished. His reduction after Theorem 9.7 means map reduction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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