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.

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.
$\endgroup$
3

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$ yesterday
  • $\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.
    yesterday
  • $\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.
    yesterday
  • $\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.
    yesterday
  • $\begingroup$ Yes, I totally agree with you. Usually, when I write a solution, I will write the formal definition following by casual comments. $\endgroup$ yesterday
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$ yesterday
  • $\begingroup$ Take it as an exercise. $\endgroup$ yesterday

Your Answer

Audra Jacot is a new contributor. Be nice, and check out our Code of Conduct.

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.