0
$\begingroup$

Let $\text{NOT-SELF} = \{\langle M \rangle : M \text{ is a TM that does not accept } \langle M \rangle \}$. How do you prove the following claim?

If $Q$ is a TM so that $L(Q) \subseteq \text{NOT-SELF}$, prove that $\langle Q \rangle \in \text{NOT-SELF}$.

$\endgroup$
1
$\begingroup$

Hint: If $\langle Q \rangle \notin \text{NOT-SELF}$ then $\langle Q \rangle \notin L(Q)$, and so $\langle Q \rangle \in \text{NOT-SELF}$.

$\endgroup$
1
$\begingroup$

In general, this problem is undecidable: that is, there is no general algorithmic solution.

Yuval gives a good answer for the specific question. Here are some general tips for showing the subset relation, that is, that $L_1 \subseteq L_2$:

  1. Induction on word length. Show that the smallest string in $L_1$ is in $L_2$ and that having one string. This is most effective when there's some sort of inductive structure to the languages you are looking at.

  2. Paths to accepting states. Look at how a word is actually accepted by your first machine, the states it travels through and what your tape looks like. For each step, show that you can do an equivalent step in the second machine which won't fail. The hard part is doing this abstractly enough so that it works for all words. This will usually break into a massive proof-by-cases.

  3. Forget about Turing Machines. Look at the machines, find out what languages they accept as sets, and perform pure logic on those sets. This isn't very useful if you are given a random TM, but is handy if you know what one TM figures out. For example, if you realize that $L_1$ is the set of all primes larger than 10, and $L_2$ is the set of all odd positive integers, then it's pretty easy to show that $L_1 \subseteq L_2$

$\endgroup$
  • $\begingroup$ Just a heads up. You might want to modify your answer since the question has been heavily modified and rewritten for the sake of much needed clarity. In the process, it changed quite significantly. $\endgroup$ – mdxn Nov 10 '13 at 22:13

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.