2
$\begingroup$

Given:

$L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$

$L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$

I believe I've managed to show that:

  • $L_1 \in \mathcal{RE \setminus R} $ since it's easy to construct the acceptor:
U(<M>):
  if <M> is an invalid encoding of a TM:
    REJECT
  emulate M(w_0)
  if M accepts:
    ACCEPT
  if M rejects:
    REJECT

But according to Rice's Theorem $L_1\notin \mathcal{R}$.

  • $L_2 \notin \mathcal{RE}$ since $\overline{H_{TM}}\leq_{m} L_2 $ where $\overline{H_{TM}}$ is the complement of the halting problem, which we know to be unrecognizable. I defined $f( \left\langle M,w\right\rangle) = \left\langle M^{\prime}\right\rangle$ s.t.:
M'(x):
  if x==w_0:
      ACCEPT
  if <M> is an invalid encoding of a TM:
    if x==w_0:
      ACCEPT
    else
      REJECT
  emulate M(w)
  if M halts:
    REJECT

These two proof attempts are not related, but they are two parts of the same question - So first I tried showing that $L_2 \leq_{m} L_1 $ which seems intuitively correct but I couldn't work it out. Then I got to think about it and since it's quite difficult to come up with an acceptor for $L_2$ or $\overline{L_2}$ it seems to me more like that $L_2 \notin \mathcal{RE}$.

I'm pretty confident that my proof for $L_1 \in \mathcal{RE \setminus R} $ it correct, but as for $L_2$, I tried so many versions of the pseudocode for $M^\prime$ (including a reduction from $\overline{A_{TM}}$) and I still can't convince myself that I got it right.

What bothers me the most is that nothing assures me $ \left\langle M,w\right\rangle \in \overline{H_{TM}} \implies \left\langle M^\prime\right\rangle \in L_2 $: As far as $M^\prime$ concerned, it might also get a valid encoding of $M$ and some $w$ on which it halts, but if $x=w_0$, then $M^\prime$ will accept anyways, which contradicts the definition of the reduction. Am I getting something wrong?

Any help would be appreciated, and if you're impressed I haven't fully grassped the methodology behind reductions, references to better explainations (other than the classic textbook's examples) would be great as well.

EDIT:

Okay, I now understand how to show that some language is unrecognizable via reductions from $\overline{A_{TM}}\notin\mathcal{RE}$ and $A_{TM}\notin co\mathcal{RE}$.

So I tried it with $L_{2}$: $A_{TM}\leq_{m}L_{2}$ seems about right, it resembles Yuval's suggestion in the comments, but I have the same trouble I had earlier convincing myself that the reduction from $\overline{A_{TM}}$ makes sense.


$A_{TM}\leq_{m}L_{2}$

We show $f\left(\left\langle M,w\right\rangle \right)=\left\langle M^{\prime}\right\rangle$ s.t. $M^{\prime}\left(x\right)$:

M'(x):
  if x==w_0:
      emulate M(w)
  else:
    LOOP
  1. $\left\langle M,w\right\rangle \in A_{TM}\implies L\left(M^{\prime}\right)=\left\{ w_0\right\} \implies\left\langle M^{\prime}\right\rangle \in L_{2}$

  2. $\left\langle M,w\right\rangle \notin A_{TM}\implies L\left(M^{\prime}\right)=\emptyset\implies\left\langle M^{\prime}\right\rangle \notin L_{2}$

Therefore, $A_{TM}\leq_{m}L_{2}$, and since $A_{TM}\notin co\mathcal{RE} \implies L_{2}\notin co\mathcal{RE}$

In this case, both implications are intuitive and make sense.


$\overline{A_{TM}}\leq_{m}L_{2}$

We show $f\left(\left\langle M,w\right\rangle \right)=\left\langle M^{\prime}\right\rangle$ s.t. $M^{\prime}\left(x\right)$:

M'(x):
  if x!=w_0:
      emulate M(w) 
      if M accepts:
        ACCEPT
  else:
    ACCEPT

Thus:

  1. $\left\langle M,w\right\rangle \in\overline{A_{TM}}\implies L\left(M^{\prime}\right)=\left\{ w_0\right\} \implies\left\langle M^{\prime}\right\rangle \in L_{2}$
  2. $\left\langle M,w\right\rangle \notin\overline{A_{TM}}\implies L\left(M^{\prime}\right)=\overline{\left\{ w_0\right\} }\implies\left\langle M^{\prime}\right\rangle \notin L_{2}$

Therefore, $\overline{A_{TM}}\leq_{m}L_{2}$, and since $\overline{A_{TM}}\notin\mathcal{RE} \implies L_{2}\notin\mathcal{RE}$

In this case, the 2nd implication is really intuitive but the 1st one doesn't seem right.

$\endgroup$
  • $\begingroup$ In the case for $L_1$, the machine you made might loop. It doesn't always halt. If $M(w_0)$ enters a loop, then your machine loops also. $\endgroup$ – frabala Jun 9 at 23:31
  • $\begingroup$ @frabala I am aware of that. But that's why it's in $\mathcal{RE \setminus R}$. I only need to show an acceptor, not a decider. Right? $\endgroup$ – gbi1977 Jun 9 at 23:57
1
$\begingroup$

It is easy to reduce $L_1$ to $L_2$: given a Turing machine $M$ and an input $w_0$, construct another Turing machine $M'$ that runs $M$ if the input is $w_0$, and loops on any other input. Then $w_0 \in L(M)$ iff $L(M') = \{w_0\}$.

In contrast, you cannot reduce $L_2$ to $L_1$, since otherwise the halting problem would be co-r.e. Stated differently, if there is a computable reduction from $L_2$ to $L_1$, then the non-halting problem (on empty input, say) is recursively enumerable. Given a machine $M$, construct a machine $M'$ which halts if the input is $0$, and otherwise clears the tape and runs $M$. Then $M$ doesn't halt on the empty input iff $L(M') = \{0\}$. If you could computably reduce $L_2$ to $L_1$, then this would give an r.e. algorithm for deciding whether $M$ doesn't halt on the empty input.


The halting problem reduces to both $L_2$ and $\overline{L_2}$. Given a Turing machine $M$ and an input $x$:

  1. Construct a Turing machine $M'$ which on input $x$ executes $M$, and otherwise loops. Then $M$ halts on $x$ iff $L(M') = \{x\}$.
  2. Construct a Turing machine $M''$ which on input $x$ executes $M$, on input $1x$ halts, and otherwise loops. Then $M$ halts on $x$ iff $L(M'') \neq \{1x\}$.

This shows that $L_2$ is neither r.e. nor co-r.e.

$\endgroup$
  • $\begingroup$ Thanks! you made things a bit more clear to me on how to construct the code. But the result $L_1 \leq_{m} L_2 $ is still only useful to deduce that $L_2 \notin \mathcal{R} $, and I still can't find a way to show if $L_2 \in \mathcal{RE}\cup co\mathcal{RE} $ or not. $\endgroup$ – gbi1977 Jun 10 at 10:32
  • $\begingroup$ I suggest you keep trying. $\endgroup$ – Yuval Filmus Jun 10 at 13:33
  • $\begingroup$ Do you mean: $M^{\prime\prime}(w_0)$ will emulate $M(w)$, and if $M$ halts, $M^{\prime\prime}$ rejects; $M^{\prime\prime}(1w_0)$ (or any other fixed word which is not $w_0$) accepts; And in any other case, $M^{\prime\prime}$ loops; Is this how $M^{\prime\prime}$ operates? $\endgroup$ – gbi1977 Jun 10 at 16:45
  • $\begingroup$ I used $1x$ for $w_0$. $\endgroup$ – Yuval Filmus Jun 10 at 17:46
  • 1
    $\begingroup$ Right, that’s the idea. $\endgroup$ – Yuval Filmus Jun 11 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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