1
$\begingroup$

About the language $L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$

I want to determine if it is in RE / coRE or neither.

I think that I found a mapping reduction from $\overline{A_{TM}}$ to $L$, where $\overline{A_{TM}}=\{<M,w>|M~is~a~TM~and~M~does~not~accept~w\}$:

Define $f(<M>)=<N_{M,w}>$ as follows:

$N_{M,w}=$ "On input $x$:

  1. If $x='01'$, accept
  2. Run $M$ on $w$ and do as $M$ does."

So if $<M,w>\in\overline{A_{TM}}$ we have $L(N_{M,w})=\{01\} \in L$.

If $<M,w>\notin\overline{A_{TM}}$ we have $L(N_{M,w})=\Sigma^* \notin L$

But I don't know if I am able to construct a TM for $\overline{L}$ or find another reduction from a RE language to $L$.

Any help?

Thanks!

$\endgroup$
2
  • $\begingroup$ You can your Rice theorem for the other direction. $\endgroup$ Nov 29, 2022 at 13:32
  • 1
    $\begingroup$ Thank you for the answer! :) $\endgroup$
    – Geo
    Dec 1, 2022 at 10:42

1 Answer 1

1
$\begingroup$

If you want ro prove that L-complement is RE, you can construct a TM which enumerates L-complement. L-complement contains the M's which are not some Turing machine's code or they are code of Turing machines that accept some input which is not in the form of 0'1' . If such an input exists, It can be computably found. So L-complement is re because both following sets are re:

A = { < M > | M is not a Turing machine code.}

B = {< M > | M is a Turing machine which accepts some input which is not in the form of 0'1'}

And

L-complement = A U B

It is a theorem that if A and B are r.e sets, then so is A U B

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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