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?

14

Zastanawiam się, jak to się stało, że język jest w następujący .R

L.M.1={⟨M.2)⟩|M.2) jest TM, i L.(M.1)=L.(M.2)), i |⟨M.1⟩|>|⟨M.2)⟩|}

(Wiem, że jest to ponieważ istnieje odpowiedź na to pytanie wielokrotnego wyboru, ale bez wyjaśnienia).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∉rdzeń∪RE

Dzięki!

computability undecidability Józef
źródło

Odpowiedzi:

14

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 .RR

Dave Clarke
źródło
9
Ważna uwaga: mimo że język jest rozstrzygalny, funkcja f ( M ) = L M, 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.1fa(M.)=L.M.
templatetypedef