Oto krótki szkic pokazujący, że nie ma maszyny Turinga, która decydowałaby o rozstrzygnięciu dowolnej klasy problemów.
Powinienem wyjaśnić, co rozumiem przez klasę problemów: klasę problemów Tjest maszyną Turinga, która wylicza elementy (powiedzmy liczby naturalne) zestawu rekurencyjnie wyliczalnego jeden po drugim, tak że każdy element zestawu jest ostatecznie drukowany. Problem intuicyjnie uchwycony przezT(n) is: ”to liczba n w tym zestawie? ”. To wychwytuje typowe problemy w dziedzinie obliczalności, takie jak„ czy i jest indeksem maszyny Turinga, która zatrzymuje się przy pustym wejściu? ”.
Załóżmy, że była maszyna M który jako dane wejściowe przedstawia klasę problemów T odpowiedział true jeśli ta klasa jest rozstrzygalna i false Inaczej.
Teraz weź dowolną maszynę Turinga T. Budujemy następującą klasę problemówT′ W następujący sposób:
- Symulować T.
- Gdyby T zatrzymuje się, wyliczyć wskaźniki maszyn Turinga, które zatrzymują się przy pustych danych wejściowych.
Teraz jest jasne, że jeśli T więc zatrzymuje się M(T′) zwroty false, ponieważ zbiór wskaźników zatrzymujących maszyny Turinga nie jest zbiorem rozstrzygalnym (rekurencyjnym).
Gdyby Twięc nie zatrzymuje sięT′nie wylicza żadnych liczb, co sprawia, że jest to dokładnie klasa problemów bez żadnych indeksów! W związku z tymM(T′) odpowiedzi true, ponieważ ta klasa jest rozstrzygalna (przez maszynę, która zawsze odrzuca).
W związku z tym, M(T′) zwroty true iff T nie zatrzymuje się i falseInaczej. Tak więc istnienieM pozwala nam rozwiązać problem zatrzymania dowolnej maszyny T, co jest sprzecznością.