0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – Raphael ♦
    Nov 21, 2018 at 16:28
  • $\begingroup$ Hi @Raphael, I have edited the question I think it is more precise now $\endgroup$
    – eatfood
    Nov 22, 2018 at 14:18

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Hi, should the 3rd point be "it accepts every other string"? $\endgroup$
    – eatfood
    Nov 22, 2018 at 14:55
  • $\begingroup$ @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. $\endgroup$
    – chi
    Nov 22, 2018 at 15:09
  • $\begingroup$ 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$. $\endgroup$
    – eatfood
    Nov 22, 2018 at 15:16
  • $\begingroup$ 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. $\endgroup$
    – eatfood
    Nov 22, 2018 at 15:17
  • $\begingroup$ @eatfood I think you are right, let me check. I think I missed one negation at one point. $\endgroup$
    – chi
    Nov 22, 2018 at 15:17

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