Skip to main content
2 of 6
edited body
  • 55
  • 6

Mapping reducing $\overline{L_{u}}$ to $L_{\epsilon}$

I am struggling with a mapping reduction that I think cannot be correct, but I'm not able to say exactly what's the problem.

Let $\overline{L_{u}}= \{\langle M,w\rangle \; | \; \text{M rejects w}\}$ and $L_{\epsilon} = \{M \; | \; \epsilon \in L(M) \}$.

I have started with this:

  1. $\langle M,w \rangle \in \overline{L_{u}}$ iff $f(\langle M,w \rangle) \in L_{\epsilon}$

My $f$ is a computable function that transforms $\langle M,w \rangle$ in the following TM $M'$:

"On input x, 
     if x != epsilon, Accept
     otherwise run M with input w,
          if M accepts w, Reject
          otherwise, Accept"

Now, assuming $w = \epsilon$, if $M$ accepts $w$ then $\langle M,w \rangle \notin \overline{L_{u}}$, and $\epsilon \notin L(M')$. If $M$ rejects $w$ then $\langle M,w \rangle \in \overline{L_{u}}$ and $\epsilon \in L(M')$.

If $w \neq \epsilon$, then we don't need to be dependent of $\overline{L_{u}}$. So we can accept without any risk.

So, with this in mind, 1. holds and we have a mapping reduction. Since $\overline{L_{u}}$ is not T-recognisable, so is $L_{\epsilon}$.

Now, the problem. Let's construct a TM $M_\epsilon$ that recognises $L_\epsilon$.

"On input M (code of a TM),
    run M with input epsilon using the TM for L_u (let's use the Universal Turing Machine - UTM),
       if it accepts, Accept
       otherwise, Reject"

This TM $M_\epsilon$ should be able to recognise $L_\epsilon$. That is, given $M$ such that $\epsilon$ is in $L(M)$, $M_\epsilon$ halts and accepts, otherwise, the machine may or may not halt.

Since $\overline{L_{u}}$ is T-recognisable (one may call it recursively enumerable), $UTM$, if given an $M$ and a $w$, if $M$ accepts $w$ then it will halt and accept. If $w = \epsilon$, this means that $M_\epsilon$ will halt and accept if $M$ accepts $\epsilon$. This means that $L_\epsilon$ must be recursively enumerable, but the reductions says otherwise.

Now I'm unsure of what definition I have wrong, or what detail I'm overlooking ...

  • 55
  • 6