If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Nierozstrzygalne 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
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.