2 of 6
edited body
PedrV
• 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 ...

PedrV
• 55
• 6