Czy zatrzymanie problemu jest obliczalne dla poszczególnych danych wejściowych / założeń

Z mojego rozumienia dowodu, że problemu zatrzymania nie można obliczyć, problemu tego nie da się obliczyć, ponieważ jeśli mamy program P (x), który oblicza, czy program x zatrzymuje się, czy nie, mamy paradoks, gdy P podaje się jako dane wejściowe do to samo P, mając: P (P), próbując zdecydować, czy P zatrzymuje się, czy nie używać samego P.

Więc moje pytanie brzmi: czy zatrzymanie problemu jest obliczalne przez program P dla wszystkich innych programów używanych jako dane wejściowe, ale sam P? Innymi słowy: czy zatrzymanie problemu nie jest możliwe do obliczenia tylko w tym szczególnym przypadku, czy dowód jest bardziej ogólny i czegoś mi brakuje?

Jeśli jest dowolną funkcją obliczalną, to , zdefiniowane jako$f$$g$

jest również obliczalny dla dowolnego wyboru .$k,v$

Zasadniczo, jeśli masz program który oblicza dla wszystkich , z wyjątkiem , możesz "naprawić" ten przypadek (np. Używając an ) i uzyskać inny program który oblicza dla wszystko . g ( n ) n n = k P g $P'$$g(n)$$n$$n=k$if then else$P$$g(n)$$n$

Dlatego jeśli można obliczyć funkcję zatrzymania „z wyjątkiem jednego przypadku”, można również obliczyć funkcję zatrzymania (bez wyjątków). Dzięki temu można uzyskać jak zwykle sprzeczność.

Wniosek: nie, nie możesz zdecydować o problemie zatrzymania „z wyjątkiem jednego przypadku” (ani „z wyjątkiem skończonej liczby przypadków”).

czy problem zatrzymania jest obliczany przez program P dla wszystkich innych programów używanych jako dane wejściowe, ale sam P?

Nie Rozważmy nieskończoną sekwencję programów , gdzie jest „przesunięcie głowicy  placów w prawo, a następnie  placów w lewo, a następnie zrobić dokładnie to, co zrobi.” Każdy z tych programów generuje dokładnie to samo wyjście co  dla każdego wejścia (włączając w to zapętlanie na zawsze, jeśli  zapętla się na zawsze), ale wszystkie są różnymi programami.P i i i P P $P_1, P_2, \dots$$P_i$$i$$i$$P$$P$$P$

Nie można tego obejść, wymagając od tylko pracy na programach, które nie są funkcjonalnie równoważne z sobą, ponieważ ta właściwość jest również nierozstrzygalna. Być może problem będzie rozstrzygalny, gdy ograniczy się do tych przypadków (choć podejrzewam, że nie), ale zestaw instancji jest nierozstrzygalny, więc nie można w rzeczywistości wykonać ograniczenia.$P$

Istnieją algorytmy pokazujące, że niektóre klasy programów zatrzymują się lub nie zatrzymują. Na przykład,

• Możliwe jest algorytmiczne ustalenie, czy program modelujący maszynę o stanie skończonym zatrzymuje się.
• Możliwe jest arytmetyczne ustalenie, czy zatrzymująca się maszyna liniowa ograniczona liniowo
• Jeśli wiesz, w jakiej klasie złożoności znajduje się program, wiesz, że program zatrzymuje się na skończone dane wejściowe.

Chociaż nie ma algorytmu określającego, czy dowolny program się zatrzymuje, większość kodu została zaprojektowana albo do zatrzymania (jak większość podprogramów), albo do zatrzymania (jak nieskończona pętla do obsługi zdarzeń), i możliwe jest algorytmiczne określenie, który jest który. Innymi słowy, można mieć algorytm, który odpowiada albo „zatrzymanie”, „nie zatrzymuje się” lub „nie wiem”, a taki algorytm może być przeznaczony na pokrycie wystarczającej ilości programów, że byłoby użyteczne.

Dowody sprzeczności nie muszą być wyczerpujące , wystarczy jeden kontrprzykład. Dowód, że problem zatrzymania jest nierozstrzygalny, przedstawia jeden przykład P, dla którego nie można ustalić właściwości zatrzymania. Dowód ten nie stwierdza, że ​​P jest jedynym takim programem, w rzeczywistości mogą istnieć niezależne dowody konstruujące zupełnie różne klasy P.

Dowód jest rzeczywiście bardziej ogólny: problem zatrzymania jest szczególnym przypadkiem twierdzenia Rice'a , które stwierdza

$\Phi$

$A$$B$$\Phi(A)$$\Phi(B)$

$x$$x$

Państwo może uzyskać pewne rezultaty ograniczając przestrzeń programów, które chcesz pracować, jeśli ograniczenia te muszą być dość drastyczne. Na przykład, jeśli masz gwarancję, że program, który otrzymujesz, zatrzymuje się w ciągu 100 kroków lub działa wiecznie, decydując, czy program się zatrzyma, stanie się łatwy.

$N$$k$$BB(k)$

Niech R będzie dowolnym rekurencyjnie wyliczalnym, ale nierekurencyjnym zbiorem. Istnieje nieskończenie wiele takich zestawów. Niech T będzie maszyną Turinga, która zatrzymuje się na wejściu k wtedy i tylko wtedy, gdy k znajduje się w R. Taki T istnieje dla dowolnego zbioru rekurencyjnie wyliczalnego. Niemożliwe jest napisanie programu, który może rozwiązać problem zatrzymania dla tego T. Jest tak, ponieważ każdy algorytm określający, czy T zatrzymuje się, dałby algorytm określający członkostwo w R, co jest niemożliwe, jeśli R nie jest rekurencyjny. Ponieważ istnieje nieskończenie wiele takich R, z których każda daje różne maszyny Turinga, istnieje nieskończenie wiele maszyn Turinga, na których nie powiódłby się żaden program zatrzymania P.