2
$\begingroup$

For a property $P$ of languages, which we identify with the set of languages satisfying it, let $L_P = \{ \langle M \rangle \mid L(M) \in P \}$ be the set of descriptions of Turing machines whose languages satisfy $P$.

How can we prove that there's no property $\displaystyle P\subseteq RE $ for which $ L_{P}=K $, where $K=\{\langle M \rangle \mid M(\langle M \rangle)\!\downarrow\} $?

$\endgroup$
  • $\begingroup$ Then, can you write down a property $ P $ for $ L_P=K $ ? $\endgroup$ – Sikelef Jan 7 '17 at 15:30
  • $\begingroup$ I know that K is recursively enumerable, but that's not the question ( don't care about the title, it changed it's self , I don't know what happened) . The question is if there is property P such that $ L_P=K $ .You must definately know what a propery is in order to find an answer to this question. Thank you. $\endgroup$ – Sikelef Jan 7 '17 at 16:38
  • $\begingroup$ A language $ P $ of TM descriptions is called property iff: 1) is non-trivial and 2) for every TMs $M_1$ and $M_2$ such that $ L(M_1)=L(M_2) $ , then $ <M_1>\in P $ if and only if $<M_2>\in P $ $\endgroup$ – Sikelef Jan 7 '17 at 16:57
  • $\begingroup$ $L_P=\{ <M> | L(M)\in P\} $ $\endgroup$ – Sikelef Jan 7 '17 at 17:07
  • $\begingroup$ These definitions are well known in advanced computation theory. If you lack knowledge, it would be better not to answer. $\endgroup$ – Sikelef Jan 7 '17 at 17:09
2
$\begingroup$

According to the recursion theorem, there is a Turing machine $M$ such that $L(M) = \{\langle M \rangle\}$. If $P$ is a property such that $L_P = K$ then $\langle M \rangle \in K$ implies that $L(M) = \{ \langle M \rangle \} \in P$. Now it is easy to construct a different machine $M' \neq M$ such that $L(M') = \{ \langle M \rangle \}$. Since $L(M') \in P$ and $L_P = K$, we must have $\langle M' \rangle \in K$, yet $M'$ doesn't halt on $\langle M' \rangle$.

Note that this solution doesn't use the condition $P \subseteq RE$.

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