Problem Detail: I wonder how come that the following language is in $mathrm R$. $L_{M_1}=Bigl{langle M_2rangle ;Big|;; M_2 text{ is a TM, and } L(M_1)=L(M_2), text{ and } |langle M_1rangle| > | 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!
Asked By : Jozef
Answered By : Dave Clarke
$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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3090 Ask a Question Download Related Notes/Documents
