2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Are you aware of the language TOTAL, of all total Turing machines (ones which halt on all inputs)? $\endgroup$ May 13, 2022 at 9:41
  • $\begingroup$ Please check some examples of non-enumerable languages whose complement isn't either. $\endgroup$
    – John L.
    May 13, 2022 at 14:54
  • $\begingroup$ In fact, such pairs cannot be enumerated even if we have an oracle machine that decides whether a given TM accepts a given word. $\endgroup$
    – John L.
    May 16, 2022 at 13:43

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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) \}$? $\endgroup$ May 16, 2022 at 6:59
  • $\begingroup$ 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)\}$ $\endgroup$
    – John L.
    May 16, 2022 at 12:21
  • $\begingroup$ @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? $\endgroup$
    – John L.
    May 16, 2022 at 13:33
  • $\begingroup$ @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. $\endgroup$
    – John L.
    May 16, 2022 at 13:34
  • $\begingroup$ Yes, I totally agree with you. Usually, when I write a solution, I will write the formal definition following by casual comments. $\endgroup$ May 16, 2022 at 23:20
2
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ Thanks for reply, could you please show me how to make reduction from TOTAL problem to this problem? $\endgroup$ May 16, 2022 at 11:55
  • $\begingroup$ Take it as an exercise. $\endgroup$ May 16, 2022 at 12:21

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.