1
$\begingroup$

I know this has been a question but based on a past experience, i thought i would rewrite it so i can get input and ask questions faster.

Suppose we have $$\text{NOT-SELF}=\{\langle M\rangle \mid M \text{ is a Turing machine that does not accept }\langle M\rangle\}$$ the set of all machines that don't accept their own coding.

Let $Z$ be a TM such that $L(Z)$ is a subset of $\text{NOT-SELF}$. Prove that $\langle Z\rangle$ is an element of $\text{NOT-SELF}$.

My answer so far is very broad and I'm trying to improve it.

If $\langle Z\rangle$ is not an element of $\text{NOT-SELF}$, than $\langle Z\rangle$ can’t be an element in $L(Z)$. Since there’s a condition that $L(Z)$ is a subset of $\text{NOT-SELF}$, this contradicts so $\langle Z\rangle$ must be an element of $\text{NOT-SELF}$.

$\endgroup$
  • $\begingroup$ Z only accepts TMs that do not accept themselves (being a subset of NOT-SELF). Therefore it doesn't accept itself and is in NOT-SELF. $\endgroup$ – avakar Nov 12 '13 at 23:31
  • 1
    $\begingroup$ So you deliberately posted a duplicate? $\endgroup$ – Raphael Jan 15 '14 at 8:30
1
$\begingroup$

Assume (i) $L(Z) \subseteq \text{NOT-SELF}$ and assume towards contradiction that (ii) $\langle Z \rangle \notin \text{NOT-SELF}$.

Because of (ii) and (i) we get that $\langle Z \rangle \notin L(Z)$.

(if it was in $L(Z)$ and $L(Z)$ is a subset of $ \text{NOT-SELF}$, it must also be in $\text{NOT-SELF})$.

Thus, $Z$ does not accepts its own encoding. Thus, by the definition of $ \text{NOT-SELF}$ it should be that $\langle Z \rangle \in \text{NOT-SELF}$, which is a contradiction.

Also see the related question: Can I construct a Turing machine that accepts only its own encoding?

$\endgroup$

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.