Główna zawartość
Podstawy informatyki - program rozszerzony
Kurs: Podstawy informatyki - program rozszerzony > Rozdział 4
Lekcja 3: Rozwiązywanie trudnych problemówNierozstrzygalne problemy
Rozwiązywanie niektórych problemów trwa bardzo długo, dlatego używamy algorytmów, które podają przybliżone rozwiązania. Istnieją problemy, których komputer nigdy nie rozwiąże, nawet najpotężniejszy komputer na świecie dysponujący nieskończonym czasem: są to problemy nierozstrzygalne.
Problem nierozstrzygalny to taki, który powinien dać odpowiedź "tak" lub "nie", ale nie istnieje żaden algorytm, który udzieliłby poprawnej odpowiedzi na wszystkie dane wejściowe.
Problem stopu
Alan Turing udowodnił istnienie problemów nierozstrzygalnych w 1936 roku, znajdując ich przykład — słynny dziś "problem stopu":
Czy na podstawie kodu i danych wejściowych dany program kiedykolwiek zakończy działanie?
Przykładem może być program, który odlicza:
num ← 10
REPEAT UNTIL (num = 0) {
DISPLAY(num)
num ← num - 1
}
Program ten zostanie zatrzymany, ponieważ
num
ostatecznie przyjmie wartość 0. Porównaj to z tym programem, który zlicza:
num ← 1
REPEAT UNTIL (num = 0) {
DISPLAY(num)
num ← num + 1
}
Zlicza w nieskończoność, ponieważ
num
nigdy nie będzie równe 0.Istnieją algorytmy, które potrafią poprawnie przewidzieć, że pierwszy program się zatrzyma, a drugi nigdy. Są to proste programy, które nie zmieniają się pod wpływem różnych danych wejściowych.
Nie istnieje jednak algorytm, który potrafiłby przeanalizować kod dowolnego programu i określić, czy się on zatrzyma, czy nie.
Aby udowodnić, że taki algorytm nie może istnieć, Turing zastosował "dowód nie wprost".
Zaczynamy od wyobrażenia sobie, że istnieje algorytm, który potrafi określić zatrzymywalność programu.
Następnie proponujemy program o nazwie
HaltChecker
, który pobiera dwa dane wejściowe: kod programu oraz dane wejściowe dla tego programu. Następnie używa on hipotetycznego algorytmu stopowalności do zwrócenia wyniku "halts" lub "never".Ten schemat przedstawia wizualizację algorytmu
HaltChecker
:Gdybyśmy wprowadzili te wcześniejsze programy do
HaltChecker
, zobaczylibyśmy, że program odliczający daje wynik "halts", a program zliczający - "never". Zauważ, że program nie uruchamia tych programów, tylko patrzy na ich kod i podejmuje decyzje na podstawie struktury kodu.Teraz jednak zaproponujemy program o nazwie
Reverser
. Przyjmuje on jedną daną wejściową, kod programu. Wysyła on HaltCheckerowi
ten program zarówno jako program do przeanalizowania, jak i jako dane wejściowe dla programu. Następnie HaltChecker
określa, czy program wejściowy zatrzymuje się, gdy jest podany jako wejście. Jeśli HaltChecker
zwraca "halts", Reverser
wykonuje nieskończoną pętlę. Jeśli HaltChecker
zwróci "never", Reverser
natychmiast kończy pracę.Ten schemat blokowy przedstawia wizualizację
Reverser
:Jeśli wprowadzimy program odliczający do
Reverser
, zobaczy on, że HaltChecker
zwraca "halts" i wybierze pętlę nieskończoną.Jeśli wprowadzimy program liczący do
Reverser
, to zobaczy on, że HaltChecker
zwraca "never", a więc zadecyduje o natychmiastowym zakończeniu programu.Reverser
jest rzeczywiście dziwnym programem. Zatrzymuje się, gdy dowiaduje się, że inny program się nie zatrzymuje, i lubi trwać bez końca, gdy zauważy, że inny program się zatrzymał. Jest to dziwne, ale to nic nie szkodzi, dziwne programy mają prawo istnieć na świecie.Ale tu wszystko się rozlatuje: co się stanie, jeśli do
Reverser
wprowadzimy sam Reverser
? HaltChecker
analizuje kod Reverser
, aby określić, czy się zatrzymuje. Jeśli zdecyduje, że nie zatrzymuje się, to zwróci "never". Reverser
widzi ten wynik i natychmiast kończy pracę.Ale, chwileczkę!
HaltChecker
właśnie stwierdził, że Reverser
nigdy się nie zatrzymuje, a potem poszedł dalej i zatrzymał się. HaltChecker
nie dał nam poprawnej odpowiedzi.Co jeśli
HaltChecker
zamiast tego zwróci "halts"? Gdy Reverser
widzi ten wynik, zapętla się w nieskończoność. HaltChecker
tylko stwierdził, że Reverser
się zatrzymuje, a jednak trwało to bez końca. Po raz kolejny, HaltChecker
nie dał nam poprawnej odpowiedzi. W rzeczywistości, nie ma sposobu, aby HaltChecker
dał nam poprawną odpowiedź w tej sytuacji. W ten sposób udowodniliśmy, że doskonale poprawny algorytm przewidywania zatrzymania nigdy nie może istnieć oraz że problem zatrzymania jest nierozstrzygalny.
Zajęło mi trochę czasu, zanim naprawdę zrozumiałem, na czym polega problem zatrzymania. Jeśli też masz z tym problemy, ten film animowany może być pomocny.
Więcej nierozstrzygalnych problemów
Informatycy i matematycy odkryli wiele innych problemów niedających się rozstrzygnąć. Sporo z nich, po uproszczeniu, wygląda jak kolejny przypadek problemu stopu. Ogólnie rzecz biorąc, wszystkie problemy nierozstrzygalne dotyczą trudności w określeniu własności wejścia i wyjścia programów.
Pomocne jest uświadomienie sobie, kiedy mamy do czynienia z problemem niedeterministycznym. Możemy wtedy zaakceptować fakt, że nasz program nie może poprawnie udzielić odpowiedzi "tak" lub "nie" na wszystkie dane wejściowe, i wymyślić inne podejście.
Na przykład nasze środowisko programistyczne Khan Academy stara się unikać uruchamiania programów z nieskończonymi pętlami, aby zapobiec zawieszaniu się przeglądarki. Ale skąd możemy wiedzieć, że program ma nieskończoną pętlę? Nie możemy, to jest niedeterministyczne! Zamiast tego monitorujemy, jak długo trwają pętle, a gdy pętla trwa zbyt długo, odmawiamy wykonania kodu. Nie mamy pewności, czy pętla będzie się ciągnęła w nieskończoność, ale dla naszych celów lepiej dmuchać na zimne.
🙋🏽🙋🏻♀️🙋🏿♂️Czy masz jakieś pytania na ten temat? Chętnie na nie odpowiemy — wystarczy, że zadasz pytanie w poniższym obszarze pytań!
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji