# Is the problem of "DFA-TM-INCLUSION" recursively enumerable?

Consider the following problem:

• Input: A Turing Machine M and a DFA D.
• Question: Is $$L(D) \subseteq L(M)$$?

Of course, this problem is not decidable. Because it is known that judging whether a word belong to a Turing Machine is not decidable. If this problem is decidable, then we can write the word as regular expression and construct DFA from this regular expression, and then check the inclusion relationship between DFA and Turing Machine. So this is not decidable.

However, I feel difficult to prove or disprove whether it is recursively enumerable.

Any ideas are welcome.

New contributor
Audra Jacot is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Are you aware of the language TOTAL, of all total Turing machines (ones which halt on all inputs)? May 13 at 9:41
• May 13 at 14:54
• In fact, such pairs cannot be enumerated even if we have an oracle machine that decides whether a given TM accepts a given word. yesterday

No, $$\{\langle D,M\rangle\mid D\text{ is a DFA }\land M\text{ is a Turing Machine }\land L(D)\subseteq L(M)\}$$ is not recursively enumerable.

Let $$Z=\{0^{n}\mid n\ge0\}$$. Call a Turing Machine (TM) $$M$$ a $$Z$$-TM if $$Z\subseteq L(M)$$.

Claim. $$\{\langle M\rangle\mid M\text{ is a } Z\text{-TM}\}$$ is not recursively enumerable.
Proof (by diagonalization): Towards a contradiction suppose $$\{\langle M\rangle\mid M\text{ is a } Z\text{-TM}\}$$ is recursively enumerable. That implies there is Turing machine $$A$$ that enumerates all $$Z$$-TMs, i.e., given a natural number $$n$$ as input, $$A$$ will output (the encoding of ) a $$Z$$-TM, which is denoted by $$C_n$$ such that the set of all $$C_n$$ is the set of all $$Z$$-TMs.

Let us construct TM $$B$$ so that on input $$w$$, $$B$$ will check first whether $$w$$ contains only $$0$$s.

• If not, $$B$$ accepts. (The behavior of $$B$$ here does not matter.)
• If yes, $$B$$ computes $$n$$, the number of $$0$$s in $$w$$. Then $$B$$ will use $$A$$ to obtain $$C_n$$. Then $$B$$ will simulate $$C_n$$ on input $$0^n$$, until $$C_n$$ accepts. Then $$B$$ will run one more step and accepts.

$$B$$ is different from each $$C_n$$ for all $$n$$, but $$Z\subseteq L(B)$$. This means $$A$$ misses $$B$$ in its enumeration of all $$Z$$-TMs. $$\quad\checkmark$$

If we can enumerate all pairs of $$D$$ and $$M$$ such that $$L(D)\subseteq L(M)$$, we can further select the pairs such that $$L(D)=Z$$, since it is decidable whether $$L(D)=Z$$. Then we can enumerate $$Z$$-TMs. This contradicts the claim above.

• Almost understand but a few points need to be clarified. 1. "Z-TMs are not recursively enumerable", is it means that "given a Turing Machine description, if it belong to Z-TMs"? 2. definition about Z-TMs, is it formally $\{ M: \exists w \in Z, w \in L(M) \}$? yesterday
• 1. Yes. It is common for "a Turing machine" to mean " the encoding of a Turing machine". ""Z-TMs are not recursively enumerable" is shorthand for "the set of encodings of $Z$-TMs is recursively enumerable." 2. $\{ M: \forall w \in Z, w \in L(M)\}$ yesterday
• @AudraJacot If a proof is highly formalized, the idea may become less "intuitive". If not formalized enough, the proof could be ambiguous. It is not easy to find the right balance. I just made the answer more formal. Is this version good enough? yesterday
• @AudraJacot Next time when you post a question, you may want to tell something like which section of which textbook you are reading (also for consistent notations and terminologies) or you are preparing the final exam. yesterday
• Yes, I totally agree with you. Usually, when I write a solution, I will write the formal definition following by casual comments. yesterday

TOTAL is the problem of deciding whether a given Turing machine halts on all inputs. This problem is $$\Sigma_2$$-complete, and in particular, it is neither r.e. nor co-r.e.

Your problem is also $$\Sigma_2$$-complete. There is a simple reduction from TOTAL to your problem. In the other direction, given a pair $$(M,D)$$, you can construct a new Turing machine $$M'$$ which on input $$x$$ checks whether $$x \in L(D)$$. If so, it runs $$M$$ on $$x$$, and otherwise, it immediately halts. The new Turing machine $$M'$$ is total iff $$L(D) \subseteq L(M)$$.

• Thanks for reply, could you please show me how to make reduction from TOTAL problem to this problem? yesterday
• Take it as an exercise. yesterday