# No subset of RE captures the set of TMs halting on themselves as input

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\}$?

• Then, can you write down a property $P$ for $L_P=K$ ? – Sikelef Jan 7 '17 at 15:30
• 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. – Sikelef Jan 7 '17 at 16:38
• 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$ – Sikelef Jan 7 '17 at 16:57
• $L_P=\{ <M> | L(M)\in P\}$ – Sikelef Jan 7 '17 at 17:07
• These definitions are well known in advanced computation theory. If you lack knowledge, it would be better not to answer. – Sikelef Jan 7 '17 at 17:09

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