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

Question

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.

Answer 1

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