W przypadku maszyny Turinga , w jaki sposób zestaw maszyn które są „krótsze” niż i które akceptują ten sam język, jest rozstrzygalny?

Zastanawiam się, jak to się stało, że język jest w następujący . $\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\}$

(Wiem, że jest to ponieważ istnieje odpowiedź na to pytanie wielokrotnego wyboru, ale bez wyjaśnienia). $\mathrm R$

Natychmiast pomyślałem, że ponieważ wiemy, że sprawdzenie, czy dwie maszyny akceptują ten sam język, nie jest rozstrzygalne, pomyślałem: czy to jest natychmiastowe „Fałsz”, ale tak nie może być, ponieważ istnieje wiele maszyn Turinga, które akceptują tę samą odpowiedź i mają różne kodowanie. $L_{M_1} \notin \textrm{co-RE} \cup \textrm{RE}$

Dzięki!

computability undecidability

— Józef
źródło

$L_{M_1}$ jest w po prostu dlatego, że liczba opisów maszyn mniejszych niż dany opis maszynowego jest skończony i każdy język jest skończony w . $R$ $R$

— Dave Clarke
źródło

Ważna uwaga: mimo że język

jest rozstrzygalny, funkcja

która faktycznie decyduje o tym języku, nie jest obliczalna. Myślę, że prawdopodobnie dlatego wynik jest początkowo sprzeczny z intuicją.

L_{M_{1}}

$L_{M_1}$

f (M) = L_{M}

$f(M) = L_M$

— templatetypedef