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.

  • 1
    $\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$ – Yuval Filmus Jan 19 '17 at 14:38
  • $\begingroup$ I have tried the recrusion theory but I can not get the answer $\endgroup$ – Sikelef Jan 19 '17 at 15:20
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 19 '17 at 16:58
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 19 '17 at 17:21
  • $\begingroup$ @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? $\endgroup$ – 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$.

| cite | improve this answer | |

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.