Problem stopu
Problem z zatrzymaniem jest problemem w informatyce. Problemem jest spojrzenie na program komputerowy i ustalenie, czy program będzie działał wiecznie, czy nie. Mówimy, że program "rozwiązuje problem zatrzymania", jeśli potrafi spojrzeć na jakikolwiek inny program i stwierdzić, czy ten inny program będzie działał wiecznie, czy nie.
Na przykład, program taki jak ten:
podczas gdy Prawda. Kontynuuj;zapętli się na zawsze, ale program
podczas gdy Fałszywy: kontynuuj;zatrzymuje się bardzo szybko.
Czy istnieje program, który rozwiązuje problem zahamowania? Okazuje się, że nie ma. Udowodnimy to pokazując, że jeśli istnieje program, który rozwiązuje problem zatrzymania, to dzieje się coś niemożliwego. Więc na razie będziemy działać tak, jakby naprawdę istniał program, który rozwiązuje problem zatrzymania. Tutaj P jest funkcją, która oceni funkcję F (wywołaną argumentem I) i zwróci prawdę, jeśli będzie działała wiecznie, a false inaczej.
def P(F, I): jeśli F(I) działa wiecznie: zwróć Prawdziwą; inaczej: zwróć Fałszywą;P może przyjrzeć się każdemu programowi i dowiedzieć się, czy będzie działał wiecznie, czy nie. Używamy P do stworzenia nowego programu, który nazwiemy Q. To, co Q robi, to spojrzenie na inny program, a następnie odpowiedź na poniższe pytanie: "Jeśli uruchomimy ten program i zrobimy z niego kopię, czy będzie działał wiecznie?". Możemy zrobić Q, ponieważ mamy P. Wszystko, co musimy zrobić, to powiedzieć Q, aby stworzył nowy program, który jest starym programem patrząc na siebie, a następnie użyć P, aby dowiedzieć się, czy nowy program działa wiecznie, czy nie.
def Q(F): powrót P(F, F);Teraz robimy kolejny program R. R patrzy na inny program i pyta Q o jego odpowiedź na ten program. Jeśli Q odpowie "tak, jeśli uruchomimy ten program i każemy mu spojrzeć na jego kopię, będzie on działał wiecznie", wtedy R zatrzymuje się. Jeśli Q odpowie "nie, jeśli uruchomimy ten program i każemy mu spojrzeć na kopię samego siebie, to nie będzie działał wiecznie", wtedy R wchodzi w nieskończoną pętlę i działa wiecznie.
def R(F): if Q(F): return; //terminate else: while True: continue; //loop foreverTeraz patrzymy, co się stanie, jeśli zrobimy R. spojrzeć na kopię siebie. Mogą się zdarzyć dwie rzeczy: albo się zatrzyma, albo będzie działać wiecznie.
Jeśli uruchomienie R i zmuszenie go do spojrzenia na kopię samego siebie nie będzie działać wiecznie, to Q odpowiedział "tak, jeśli uruchomimy ten program i zmusimy go do spojrzenia na kopię samego siebie, to będzie działać wiecznie". Ale Q powiedział to, gdy spojrzał na samo R. Tak więc to, co Q faktycznie powiedział to: "tak, jeżeli uruchomimy R i zmusimy go, aby spojrzał na kopię samego siebie, to będzie działał wiecznie". Tak więc: Je±li R biegn±ce na kopii siebie samej nie biegnie wiecznie, to biegnie wiecznie. To jest niemożliwe.
Jeśli uruchomimy R i każemy mu spojrzeć na kopię samego siebie, to Q odpowiedział "nie, jeśli uruchomimy ten program i każemy mu spojrzeć na kopię samego siebie, to nie będzie działał wiecznie". Ale Q powiedział to, gdy spojrzał na samo R. Więc to, co Q faktycznie powiedział to: "nie, jeżeli uruchomimy R i zmusimy go, aby spojrzał na kopię samego siebie, to nie będzie działał wiecznie". Tak więc: Je±li R biegn±ce na kopii siebie samego biegnie wiecznie, to nie biegnie wiecznie. To też jest niemożliwe.
Nieważne, co się stanie, dostaniemy niemożliwą sytuację. Zrobiliśmy coś złego i musimy się dowiedzieć, co to było. Większość rzeczy, które zrobiliśmy, nie były złe. Nie możemy powiedzieć, że "robienie programu, który patrzy na kopię siebie samego, jest złe", ani "patrzenie na to, co powiedział inny program, a następnie wejście w pętlę, jeśli powiedział jedną rzecz, i zatrzymanie się, jeśli powiedział inną rzecz" jest złe. Nie ma sensu mówić, że nie wolno nam robić tych rzeczy. Jedyną rzeczą, którą zrobiliśmy, a która wygląda na to, że może być zła, jest udawanie, że program taki jak P istnieje w pierwszej kolejności. A ponieważ jest to jedyna rzecz, która może być zła, a coś musi być nie tak, to jest to. To jest dowód na to, że program taki jak P nie istnieje. Nie istnieje żaden program, który rozwiązuje problem zatrzymania.
Ten dowód został znaleziony przez Alana Turinga w 1936 roku.
Pytania i odpowiedzi
P: Co to jest problem Haltinga?
O: Problem Haltinga to problem w informatyce, który dotyczy programu komputerowego i określa, czy program będzie działał wiecznie, czy nie.
P: Skąd wiadomo, że program rozwiązuje problem haltingu?
O: Mówimy, że program "rozwiązuje problem haltingu", jeżeli potrafi spojrzeć na dowolny inny program i stwierdzić, czy ten inny program będzie działał wiecznie, czy nie.
P: Czy można udowodnić, że taki program nie istnieje?
O: Tak, pokazując, że gdyby istniał taki program, to stałoby się coś niemożliwego. Ten dowód znalazł Alan Turing w 1936 roku.
P: Co robi P?
O: P jest funkcją, która ocenia inną funkcję F (wywołaną z argumentem I) i zwraca true, jeżeli działa w nieskończoność, a false w przeciwnym razie.
P: Co robi Q?
O: Q analizuje inny program, a następnie odpowiada na pytanie, czy uruchomienie tego samego programu na sobie spowoduje powstanie nieskończonej pętli. Czyni to za pomocą P, aby dokonać oceny danej funkcji F.
P: Co robi R?
O: R patrzy na inny program i pyta Q o odpowiedź na temat tego konkretnego programu. Jeżeli Q odpowie "tak, jeżeli uruchomimy ten program i każemy mu patrzeć na kopię samego siebie, to będzie działał bez końca", wtedy R zatrzymuje się; jeżeli jednak Q odpowie "nie, jeżeli uruchomimy ten program i każemy mu patrzeć na kopię samego siebie, to nie będzie działał bez końca", wtedy R wchodzi w pętlę nieskończoną i działa bez końca.
P: Co się stanie, gdy zmusi Pan R do spojrzenia na siebie?
O: Mogą się zdarzyć dwie rzeczy - albo R zatrzyma się, albo będzie działał w nieskończoność - ale oba wyniki są niemożliwe, zgodnie z tym, co udowodniono, że programy takie jak P nie istnieją, więc coś musiało pójść nie tak, gdzieś po drodze do tego, żeby R spojrzał na siebie.
