# $L=\left \{ \left \langle M,D \right \rangle : M=TM\, ,\, D=DFA\, ,\, L(D)\neq \emptyset\, ,\, L(M)\subseteq L(D)\circ L(D) \right \}\notin RE$

$$L=\left \{ \left \langle M,D \right \rangle : M\, is\, a\, TM\, ,\, D\, is\, a\, DFA\, ,\, L(D)\neq \emptyset\, ,\, L(M)\subseteq L(D)\circ L(D) \right \}$$

$$L\notin R$$ which can be shown for example with Turing reduction.

I thought that I build a recognizer to $$L$$, i.e showed that $$L\in RE$$, but there is some mistake that I don't see, because $$L\in coRE$$ (and there for $$L\notin RE$$).

Here is what I wrote:

Input = <M,D> s.t M = TM , D = DFA
1. run BFS scan on the states of D
2. if the BFS in step 1 didn't find accepting sates
3.    reject <M,D>
4. else
5.     build D', which will be a DFA for L(D)∘L(D)
6.     for i = 0 to ∞
7.         for j = 0 to i
8.             for every x∈Σ^j in lexicographical order:
9.                 run M on w for i steps
10.                 if M accepts w
11.                    run D' on w
12.                   if D' accepts w
13.                      accept


What is wrong with that ?

(This is a question from an exam on computability)

• $\circ$ is the the sign for concatenation Commented Aug 1 at 15:41
• @BaderAbuRadi I not sure, but I think there is some point in what you wrote. If $L(D) = \emptyset$ then the machine should accept if $L(M) = \emptyset$ and in my previous version, I wrote to reject all x, including the current input <M,D> which may be still in $L$. I think it can be solved via using the recognizer of $\overline{E_{TM}}$ but at this point I'm a bit confused Commented Aug 1 at 16:46
• Note that $A\subseteq B$ iff $A \cap \overline{B} \neq \emptyset$. So it boils down to a nonemptiness check (given that we can complement and intersect) which we know is not decidable. Intuitively, to decide if a machine accepts some input is not possible as if it does not accept any input, we have to keep looking for an input and do not halt. Commented Aug 1 at 16:48
• In the language's definition $L(D)\neq \emptyset$. Meaning every input <M, D> where D is empty should be rejected. If $L(D)\neq \emptyset$ was not specified, then you need to consider the case of $L(D)= \emptyset$, but there is no need in the current version of the langauge. Commented Aug 1 at 16:50
• Reject <M, D> and not "all x". Commented Aug 1 at 16:54

You are accepting as soon as you find a word that is in both $$L(M)$$ and $$L(D) \circ L(D)$$; that is, you are semideciding
$$\exists w. w \in L(M) \land w \in L(D) \circ L(D)$$
$$\forall w. w \in L(M) \to w \in L(D) \circ L(D)$$
• Rice's theorem. You said it yourself: "$L \notin R$ which can be shown for example with Turing reduction." Commented Aug 1 at 16:01