# Non-recursivity of language of TMs which have equivalent TMs of smaller and larger description length

Prove that the language

$$L=\{\langle M \rangle \mid \exists M_1, M_2 : L(M_1)=L(M_2)=L(M) \text{ and } |\langle M_1 \rangle| < |\langle M \rangle| < |\langle M_2\rangle| \}$$

is not recursive.

• What do you think? What have you tried, and where did you get stuck? – Yuval Filmus Jan 19 '17 at 14:38
• I have tried the recrusion theory but I can not get the answer – Sikelef Jan 19 '17 at 15:20
• Hint: If you could decide $L$, you could compute (more or less) the Kolmogorov complexity of a string, which you shouldn't be able to do. – Yuval Filmus Jan 19 '17 at 16:58
• We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Jan 19 '17 at 17:21
• @YuvalFilmus I think I can define Kolmogorov complexity of $w$ as the shortest encoding of a TM that accepts $\{ w \}$. So if I could decide $L$, then I would be able to tell whether a specific TM that accepts some $\{ w \}$ is the shortest TM that accepts $\{ w \}$. But if it isn't the shortest, then even if I test whether all shorter TMs are in $L$, I wouldn't know which of them accept $\{ w \}$, and so it wouldn't help me in finding the Kolmogorov complexity of $w$... Am I misinterpreting your hint? – Oren Milman May 22 '19 at 12:16

First, let us notice that in the definition of $$L$$, a machine $$M_2$$ accepting the same language as $$M$$ but having a longer description always exists, so only the condition on $$M_1$$ is pertinent.
Suppose that $$L$$ were computable. Consider the following Turing machine $$T_\ell$$. The machine enumerates all Turing machines of size at least $$2^\ell$$, until it finds a machine $$M$$ such that $$\langle M \rangle \notin L$$ (such a machine must exist, since there are infinitely many computable languages but only finitely many Turing machines of size less than $$2^\ell$$). Then it transfers control to the machine $$M$$, i.e., it runs $$M$$ on the input.
By construction, $$L(T_\ell) = L(M)$$. Since $$\langle M \rangle \notin L$$, necessarily $$|\langle T_\ell \rangle| \geq |\langle M \rangle| \geq 2^\ell$$. However, by hardcoding $$\ell$$ into a Turing machine in which $$\ell$$ is an additional input, we see that $$|\langle T_\ell \rangle| = O(\ell)$$. We obtain a contradiction for large enough $$\ell$$.