Czy dowód nierozstrzygalności problemu zatrzymania oszukuje poprzez odwrócenie wyników?

Mam problem ze zrozumieniem problemu zatrzymania Turinga.

Jego dowód zakłada, że ​​istnieje magiczna maszyna która może ustalić, czy komputer zatrzyma się lub zapętli na zawsze dla danego wejścia. Następnie dołączamy inną maszynę, która odwraca dane wyjściowe i mamy sprzeczność i dlatego H nie może istnieć.$H$$H$

Obawiam się, że wydaje się, że mówimy, że odpowiedź jest zła, ponieważ ją odwróciliśmy. Analogicznie, jeśli istnieje maszyna o nazwie , która na niektórych wejściach podaje poprawną odpowiedź, a na innych błędną odpowiedź. Następnie dołączamy inną maszynę, która odwraca wynik A, więc kombinacja dwóch maszyn ma sprzeczność z definicją A. Obie maszyny generują obecnie nieprawidłowych odpowiedzi na wejściach że jest zdefiniowane do wyjściowych poprawnych odpowiedzi i wyjść poprawnych odpowiedzi na wejściach że jest zdefiniowane do wyjścia błędnych odpowiedzi. Czy byłoby to nazywane sprzecznością, a zatem nie istnieje maszyna, która na niektórych wejściach podaje poprawną odpowiedź, a na innych błędną?$A$$A$$A$$A$$A$

Wersja skrócona: Dane wyjściowe maszyn są niepoprawne lub niepoprawne, są po prostu sprzeczne, co dowodzi, że maszyna początkowa, która decyduje, czy maszyna wejściowa zatrzymuje się na danym ciągu, czy nie może istnieć.

Wersja długa : Najpierw naszkicujemy dowód (lub przynajmniej jedną jego wersję - jest ich wiele).

1. Załóżmy, że mamy Turingowi Maszyna , które określa, czy maszyna Turinga M postojów na wejściowej x , czy nie.$\mathrm{HALT}(\langle M\rangle, x)$$M$$x$
2. Korzystanie skonstruować maszyny F L I P ( ⟨ M ⟩ , x ) , która wykorzystuje H A L T , aby sprawdzić, czy M zatrzymanie na X , czy nie, a nie odwrotnie, tzn M zatrzymywane na X , F L Pętle I P , jeśli M nie zatrzymuje się na x , F L I P zatrzymuje się.$\mathrm{HALT}$$\mathrm{FLIP}(\langle M\rangle, x)$$HALT$$M$$x$$M$$x$$\mathrm{FLIP}$$M$$x$$\mathrm{FLIP}$
3. Wreszcie utworzyć TM (zabrakło dobre nazwy), które wykonuje się z opisem TM i biegnie F L I P z wejściem ( ⟨ M ⟩ , ⟨ M ⟩ ) , wysyłający co K L I Wyjścia $\mathrm{C}(\langle M \rangle)$$\mathrm{FLIP}$$(\langle M \rangle, \langle M \rangle)$$\mathrm{FLIP}$

Należy zauważyć, że tak długo, jak istnieje decydujący , każdy z tych etapów jest prosty do wdrożenia; K L I P po prostu musi używać H A L T , aby sprawdzić, co robić, i C tylko powiela swoje wejście do przekazania do F L I P .$\mathrm{HALT}$$\mathrm{FLIP}$$\mathrm{HALT}$$\mathrm{C}$$\mathrm{FLIP}$

Sprzeczność pojawia się, gdy spojrzymy na to, co się dzieje, gdy prowadzimy . Albo C zatrzymuje się, gdy podaje się go jako dane wejściowe lub nie. H A L T zadecyduje o tym:$\mathrm{C}(\langle\mathrm{C}\rangle)$$\mathrm{C}$$\mathrm{HALT}$

• Jeśli zatrzymanie na wejściu ⟨ C ⟩ , H L T powie Y e y , ale F L I P będzie pętli tak C pętla, zaprzeczając H A L T .$\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{Yes}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$
• Jeśli pętle na wejściu ⟨ C ⟩ , H L T powie N O , ale F L I P zostanie zatrzymane, tak C również zatrzymanie, zaprzeczając H A L T .$\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{No}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$

Ponieważ każdy z etapów budowy jest wyraźnie zdrowy, możemy jedynie stwierdzić, że nie może istnieć; skonstruowaliśmy przypadek, w którym bez względu na to, co mówi, H A L T nie może zdecydować, co wyprowadzić, tzn. problem jest nierozstrzygalny. Po prostu naprawdę trochę młotkując, H A L T nie może istnieć - to znaczy, że nie może być TM, która decyduje o problemie zatrzymania - ponieważ istnieje co najmniej jeden przypadek, który wyraźnie skonstruowaliśmy, w którym nie ma logicznie możliwa odpowiedź. Pamiętaj, że osoba podejmująca decyzję nie może podać złej odpowiedzi i musi coś przekazać, ale w przypadku, gdy skonstruowaliśmy, obie możliwe odpowiedzi są błędne.$\mathrm{HALT}$$\mathrm{HALT}$$\mathrm{HALT}$

Omawiasz dwa różne znaczenia „sprzeczności”.

W twojej analogii maszyna A i jej odwrócona modyfikacja są ze sobą sprzeczne w tym sensie, że ich wyjścia są zawsze inne. (Na przykład mogą zaimplementować dwie funkcje testowe na liczbach całkowitych: „ x ≤ 5?” I „ x > 5?”). Z pewnością jedna rzecz „sprzeczność” może oznaczać w codziennym użyciu, ale nie jest to logiczne dowody.

W logicznych dowodach oznacza to coś silniejszego: coś, co jest po prostu niemożliwe. Np. Funkcja, która zwraca „prawda” na wszystkich wejściach powyżej 5, a „fałsz” na wszystkich wejściach mniejszych niż 10 - to jest sprzeczne w tym silniejszym znaczeniu, ponieważ, powiedzmy, 7, jej wynik musiałby być zarówno „prawdziwy” i „fałsz”, ale to nie to samo. Argument Turinga pokazuje, że program zatrzymania jest sprzeczny w silniejszym znaczeniu: zakładając, że prowadzi do czegoś, co jest niemożliwe, lub o którym wiadomo, że jest fałszywe.

Oto kolejny dowód, że problem zatrzymania jest nierozstrzygalny. Mówimy, że program wypisuje ciąg jeśli się zatrzymuje i wypisuje x . (Jeśli program nigdy się nie zatrzymuje, to nie wypisuje żadnego łańcucha.) Zdefiniuj f ( n ) jako długość najdłuższego łańcucha, który jest generowany przez program C o długości co najwyżej n .$x$$x$$f(n)$$n$

Załóżmy, że problem zatrzymania był rozstrzygalny. Następnie można obliczyć za pomocą programu C:$f(m)$

Na wejściu przejrzyj wszystkie zatrzymujące się programy o długości co najwyżej m i określ ich wyjście; zwraca długość maksymalnej mocy wyjściowej.$m$$m$

Oznacza to, że dla każdego z , można napisać program P m , że wyjścia F ( m ) + 1 zerami. Jaka jest długość P m ? Istnieje stały szablon programu C z symbolem zastępczym, który implementuje P m ; symbol zastępczy powinien być wypełniony stałą m . Określenie m zajmuje | m | znaki (tutaj | m | jest długością dziesiętnej reprezentacji m ), gdzie | m | ≈ log $m$$P_m$$f(m)+1$$P_m$$P_m$$m$$m$$|m|$$|m|$$m$ . Szablon przyjmuje pewną stałą liczbęznaków T , więc długość P m wynosi T + log 10 m . Jeśli wybierzemy m wystarczająco duże (wystarczyłoby m = 2 T ), otrzymamy T + log 10 m ≤ m , a zatem f ( m ) jest co najmniej rozmiarem ciągu wyjściowego o P m , tj. F ( m ) ≥ f ( m ) + $|m| \approx \log_{10} m$$T$$P_m$$T + \log_{10} m$$m$$m=2T$$T + \log_{10} m \leq m$$f(m)$$P_m$$f(m) \geq f(m) + 1$. Doszliśmy do sprzeczności.