Rozstrzygalność i rekursywna enumerability

Question

Powiedzmy, że istnieją maszyny Turinga M1, M2, M3, języki, które uznają, odpowiednio, L (M1), L (M2) i L (M3). Następujący język L = {(M1, M2, M3): L (M1), L (M2) i L (M3) nie są równe} Czy język jest rozstrzygalny? Rekursywnie przeliczalne? Albo nie?

Answer 1

Niech M M _i, być maszyna, która symuluje uruchomiony jakiś inny maszynowy M _i na wejściu I i zwraca true jeśli M _i ostatecznie przystaje na I i pętle zawsze inaczej.

Niech M _∞ będzie trywialną maszyną, która po prostu zapętla się na zawsze.

Następnie (M _{M i, że} M _∞ M _∞) jest L IFF M _ı postojów na wejściu I.

Zmniejsza to rozstrzygalność problemu zatrzymania do rozstrzygalności L, a zatem L jest nierozstrzygalny.

=============

Następnie niech udowodnić, że L nie jest rekurencyjnie przeliczalny przez sprzeczności.

Załóżmy, że L jest rekurencyjnie przeliczalny, więc istnieje Maszyna Turinga M takie, że jeśli M _i, M _j i M _k są trzy Maszyna Turinga, których odpowiednie języki nie są sobie równe, a następnie M będzie w końcu wypluł potrójny (M _i, M _j, M _k).

Rozważmy teraz modyfikację M, zwaną M ', która jest definiowana przez przyjęcie M i dodanie wartości (M, M', M ') do L (M'). Ważne pytanie, które należy zadać, to czy (M, M ', M') znajduje się w L? Cóż, jeśli (M, M ', M') jest w L, to L (M) nie może być równe L (M ') (w przeciwnym razie nie pasowałoby do definicji L), więc L (M) nie może zawierać (M, M ', M') (ponieważ jest to jedyna modyfikacja, którą wprowadziliśmy). I odwrotnie, jeśli (M, M ', M') nie ma w L, to L (M)! = L (M ') (ponieważ dodaliśmy tę flankę do L (M')), więc musi ona być w L (M), ponieważ języki nie są równe.

Tak więc doszliśmy do paradoksu, który sugeruje, że M nie może istnieć, a zatem L nie jest rekurencyjnie przeliczalne.