14
$\begingroup$

I wonder how come that the following language is in $\mathrm R$.

$L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a TM, and } L(M_1)=L(M_2), \text{ and } |\langle M_1\rangle| > | \langle M_2 \rangle| \Bigr\} $

(I know that it's in $\mathrm R$ since there's an answer for this multi-choice question, but without explanation).

I immediately thought that the $L_{M_1} \notin \textrm{co-RE} \cup \textrm{RE}$ since we know that checking if two machines accept the same language is really not decidable, I came to think: is it immediate "False", but it can't be since there's a lot of Turing machines who accepts the same answer and have different codings.

Thanks!

$\endgroup$
14
$\begingroup$

$L_{M_1}$ is in $R$ simply because the number of machine descriptions smaller than a given machine description is finite and any finite language is in $R$.

$\endgroup$
  • 9
    $\begingroup$ An important note: although the language $L_{M_1}$ is decidable, the function $f(M) = L_M$ that actually finds the decider for this language is not computable. I think this is probably why the result is initially counterintuitive. $\endgroup$ – templatetypedef Aug 8 '12 at 17:47

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.