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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
1
  • 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, 2012 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.