# Prove that $L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$ not recursively enumerable [duplicate]

Past year paper question:

Let $$M_i$$ denote the Turing machine with code $$i$$ using the alphabet $$\Sigma=\{a,b\}$$.

Show that the following language is not recursively enumerable:

$$L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$$

I tried to show that we can reduce $$L_e$$, the set of Turing machines that accept no strings, to $$L$$. To do this, I need to find a transformation $$f$$ such that is $$\mathrm{Lang}(M)$$ is empty, then the machine represented by $$f(M)$$ has some string $$x$$ but not $$xx$$, and if $$\mathrm{Lang}(M)$$ is not empty, then the machine represented by $$f(M)$$ contains $$xx$$ if it contains $$x$$.

But I am not sure how to find such a transformation. Can someone show a transformation to solve this problem?

## marked as duplicate by Raphael♦Nov 21 '18 at 16:29

• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Nov 21 '18 at 16:28
• Hi @Raphael, I have edited the question I think it is more precise now – eatfood Nov 22 '18 at 14:18

First, recall that the problem "$$L(M)\neq\emptyset$$" is semidecidable.

Define $$f(M)$$ as $$a^i$$ where $$M_i$$ is a TM such that

• it accepts $$aa$$ iff $$L(M)\neq\emptyset$$,
• it accepts any other string (including $$a$$).

For the first step: when $$M_i$$ receives $$aa$$ as input, it semi-decides $$L(M)\neq\emptyset$$. If that holds, the semi-decider halts in finite time, so $$M_i$$ can accept. If that does not hold, the semi-decider diverges, making $$M_i$$ diverge. This is fine, since $$aa$$ is not accepted.

Note that we never reject $$aa$$, because we do not have a full decider for $$L(M)\neq\emptyset$$. This however does not matter: we do not have to reject $$aa$$, we only have to avoid accepting it, and diverging suffices.

• Hi, should the 3rd point be "it accepts every other string"? – eatfood Nov 22 '18 at 14:55
• @eatfood No, why? If you do that, then $f(M)$ would accept both $aaa$ and $aaaaaa$, always satisfying the condition in $L$ (since $x$ can be $aaa$). In that case the reduction would no longer work. – chi Nov 22 '18 at 15:09
• But in that case, if $L(M)$ empty, then $f(M)$ would accept $a$ and not $aa$, so encoding of $f(M)$ in $L$. And if $L(M)$ is not empty, then $f(M)$ would accept $aa$ and not $aaaa$, and so encoding of $f(M)$ would also be in $L$. – eatfood Nov 22 '18 at 15:16
• I was thinking that if the 3rd point was changed to "accept all other strings", then:We reduce $L_e$ to $L$. Then $L_e$ not RE implies $L$ not RE. Let $M$ be given. We define $M'$ as follows: if input is $a$, accept. if input is $aa$, if $L(M)=\emptyset$, we accept, else reject. accept all other inputs. Then define $f(M)=a^i$ where $i$ is the encoding of $M'$. Then if $L(M)=\emptyset$, $M'$ accepts every string except $aa$, so $f(M) \in L$. If $L(M) \neq \emptyset$, then $M'$ accepts all strings, so $f(M) \notin L$. So if $L_e$ is reduced to $L$, hence $L$ is not RE. – eatfood Nov 22 '18 at 15:17
• @eatfood I think you are right, let me check. I think I missed one negation at one point. – chi Nov 22 '18 at 15:17