Reduce instances of a-Turing-machine-does-not-accept-a-string to Turing machines that accept the empty string

Question

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 $L_{u}= \{\langle M,w\rangle \mid M\text{ accept }w\}$, $\overline{L_{u}}= \{\langle M,w\rangle \mid M\text{ does not accept }w\}$ and $L_{\epsilon} = \{M \mid \epsilon \in L(M) \}$.

(Part 1)

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

---

(Part 2)

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 as a component the Universal Turing Machine - UTM),
       if it accepts, Accept
       if it rejects, 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. But if halts and rejects $\epsilon$, then $M_\epsilon$ also rejects.

Since $L_{u}$ ($\{\langle M,w\rangle \; | \; \text{M accepts w}\}$) is T-recognisable (one may call it recursively enumerable), and we are using the machine that recognises the language $L_u$, with the modification of always using $w = \epsilon$ to construct $M_\epsilon$ we know that $M_\epsilon$ will recognise $L_\epsilon$.

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

Answer 1

$L_\epsilon$ is recursively enumerable whereas $\bar{L_u}$ is not. If a language $L_1$ can be reduced to another language $L_2$ then the following things hold:

1. if $L_1$ is not T-recognizable then $L_2$ is not T-recognizable.
2. if $L_2$ is recursively enumerable then $L_1$ is recursively enumerable.
3. if $L_1$ is recursively enumerable then $L_2$ may or may not be recursively enumerable.
4. if $L_2$ is not T-recognizable then $L_1$ may or may not be T-recognizable. This is what's happening in your case.

Answer 2

I decided to answer my own question since the answers given are not fully correct, maybe because of my confusing question at first. Nonetheless, thanks to @JohnL and @avasuilia for, their answers, making me see my mistake. Also, as said above, in the original question, I should have been more explicit about some terms. That caused the question to have this answer as pointed by @JohnL as the correct solution. However, that solution was not the one that I was expecting, so I am responding to the edited question, that was what I meant at first.

Point 1. from @JohnL is pretty much all that is needed to see the mistake, but I will elaborate further.

First, let’s try to reduce $\overline{L_{u}}$ to $\overline{L_{\epsilon}}$. That is:

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

Let $f$ be a computable function that transforms $\langle M,w \rangle$ in the following TM $M_1$:

“On input x,
   If x != epsilon, Accept
   Otherwise,
         Run w on M, if M accepts w, Accept
                     if M rejects w, Reject”

Let x be different than $\epsilon$. If so, it doesn’t matter the result of $\langle M,w \rangle \in \overline{L_{u}}$ since it will not affect the iff.

If $x = \epsilon$ and $\langle M,w \rangle \notin \overline{L_{u}}$, meaning $M$ halts and accepts $w$, then $M_1$ accepts $\epsilon$. This is the expected behaviour.

If $x = \epsilon$ and $\langle M,w \rangle \in \overline{L_{u}}$, meaning $M$ halts and rejects $w$, then $M_1$ rejects $\epsilon$. This is the expected behaviour. But it may happen that $M$ doesn’t halt (as far as we know), and in that case $\langle M,w \rangle \in \overline{L_{u}}$ also holds. In this case, $M_1$ will be in the same case.

Does this break the if and only if? No. The complement of $L_\epsilon$ is the following: $\{M \; | \; \epsilon \notin L(M) \}$. This means that $M$, when given $\epsilon$ may or may not halt, but if halts will rejects. $L_\epsilon$ is $\{M \; | \; \epsilon \in L(M) \}$, and for this to happen, $M$ must halt to accept.

Let’s sum this up. $M$ not halting on $w$ causes $M_1$ to also not halt. This means that $\langle M,w \rangle \in \overline{L_{u}}$ is verified by the definition of $\overline{L_{u}}$, and $f(\langle M,w \rangle) \in \overline{L_{\epsilon}}$ is also verified, by the definition of $\overline{L_{\epsilon}}$.

So we have a mapping reduction from $\overline{L_{u}}$ to $\overline{L_{\epsilon}}$.

---

Now the reduction in the question:

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

We will follow the same principle as $M_1$. Let $M_2$ be:

“On input x,
   If x != epsilon, Accept
   Otherwise,
         Run w on M, if M accepts w, Reject
                     if M rejects w, Accept”

Let x be different than $\epsilon$. If so, it doesn’t matter the result of $\langle M,w \rangle \in \overline{L_{u}}$ since it will not affect the iff.

If $x = \epsilon$ and $\langle M,w \rangle \notin \overline{L_{u}}$, meaning $M$ halts and accepts $w$, then $M_2$ rejects $\epsilon$. This is the expected behaviour.

If $x = \epsilon$ and $\langle M,w \rangle \in \overline{L_{u}}$, meaning $M$ halts and rejects $w$, then $M_2$ accepts $\epsilon$. This is the expected behaviour. But it may happen that $M$ doesn’t halt (as far as we know), and in that case $\langle M,w \rangle \in \overline{L_{u}}$ also holds. In this case, $M_2$ will be in the same case (not halting as far as we know).

Does this break the if and only if? Yes. Now we are not talking about the complement, we are talking about $L_\epsilon$. In this case, $M$ must accept $\epsilon$, and to do this, it must halt.

Let’s sum up this part. $M$ not halting on $w$ causes $M_2$ to also not halt. This means that $\langle M,w \rangle \in \overline{L_{u}}$ is verified, but $f(\langle M,w \rangle) \in L_{\epsilon}$ is not verified.

So, we don’t have a mapping reduction from $\overline{L_{u}}$ to $L_{\epsilon}$.

---

So, what we got from this, is that $L_\epsilon$ is T-recognisable (recursively enumerable), and part 2 of the question is correct. Also $\overline{L_{\epsilon}}$ is not T-recognisable.

In a nutshell

I has not being careful about the definition of complements of languages, and not being careful about the not halting (as far as we know).

I’m not marking this as solved because I would appreciate some thoughts on my answer.