# For a Turing Machine $M_1$, how is the set of machines $M_2$ which are "shorter" than $M_1$ and which accept the same language decidable?

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!

$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$.
• 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. Aug 8, 2012 at 17:47