0
$\begingroup$

First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$ is RE. I tried to construct a Turing machine:

Input: Code(M);
L_e_TM(Code(M))
    for all words w of binary strings
        simulate M on w, 
            if M accept w then return true;
    end for
end

Since we do not have to care about whether it halts or not, so we can use it to recognize $L_1$. But surely, this is language is not recursive which can be shown by reduction from the halting problem or by Rice's theorem. But when we consider the complement of this language (for simplicity, we think all binary strings are valid Turing machine codes, otherwise we can just add a decider to check whether it is one recursively which will not affect the main result), $$L_{\emptyset}:=L_\exists^\complement=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts no input}\}.$$ Similar we can just change the code above inside the for-loop:if M accept w then return false. Then both are in RE. Then they are in R? What was wrong? I thought there must be something wrong with the Turing machine code, but we are not talking about recursiveness, so I don't think the machine will not do the job to check whether it is in $L_\exists$ or not. Somewhere, I have seen $L_\exists$ is RE. Hence,

Furthermore, consider

$$L_\forall=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts all inputs}\}$$ and $$L_\forall^\complement=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts not all inputs}\}.$$ Are they both non-RE or one is RE and the other not?

$\endgroup$
  • 2
    $\begingroup$ A simple way to construct a language that's neither RE nor co-RE is to take a language that's not RE and a language that's not co-RE and "glue them together". For example $\{\langle M_1\rangle;\langle M_2\rangle;w\mid M_1(w)\text{ halts and }M_2(w)\text{ does not}\}$. $\endgroup$ – David Richerby Feb 6 at 14:18
0
$\begingroup$

Recall that a language is r.e. iff its complement is co-r.e. It follows that a language is neither r.e. nor co-r.e. iff its complement is neither r.e nor co-r.e., just like a language is recursive iff its complement is.

The language $L_{\exists}$ is recursively enumerable, though not recursive. To enumerate it, simulate all Turing machines on all possible inputs, and output a Turing machine whenever it halts on some inputs. To see that it's not recursive, reduce the halting problem to it.

Your other example $L_{\forall}$, usually known as TOT, is indeed neither r.e. nor co-r.e. In fact, it is $\Pi_2$-complete. You can prove that it is neither r.e. nor co-r.e. directly, by finding appropriate reductions from the halting problem.

$\endgroup$
  • $\begingroup$ Thanks for you answer. I rethink about my program to check $L_\exists$ is r.e. It kinda does not work. Languages in RE means it can prove the membership of a word in finite time. Because we have to run through all inputs literally one by one, but what if the machine get stuck at some input before finding the/a right one? For showing $L_\forall$ is not r.e., how will a reduction from halting problem help? If we can there is a reduction from halting problem to it then we can only be sure that it is not recursive? $\endgroup$ – Upc Feb 6 at 10:29
  • $\begingroup$ You can run a machine on many inputs, or many machines on many inputs the same way you run many machines on a single input – using dovetailing. $\endgroup$ – Yuval Filmus Feb 6 at 12:01
  • $\begingroup$ It is known that the halting problem is r.e. but not co-r.e. Hence if the halting problem reduces to a language $L$, then $L$ cannot be co-r.e. $\endgroup$ – Yuval Filmus Feb 6 at 12:02
  • $\begingroup$ $L_H\leq L_H^c$ by negating the output. But $(L_H^c)^c=L_H$ is r.e., so $L_H^c$ is co-r.e. $\endgroup$ – Upc Feb 6 at 13:00
  • $\begingroup$ For the machine can run many inputs, is this consistent with the definitions? It reminds me of NP-completeness, the Karp's reduction and Cook's reduction may make differences (when NP$\neq$P), one just allows run the program one, while another allows to run several (polynomial) times. $\endgroup$ – Upc Feb 6 at 13:10

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.