Informatyka i programowanieGranice obliczeń — problemy łatwe, trudne i niemożliwe

Busy Beaver rośnie szybciej niż każda funkcja obliczalna

Funkcja Busy Beaver jest zdefiniowana za pomocą bardzo małych maszyn Turinga. W jednej z klasycznych wersji pytamy o maksymalną liczbę kroków wykonaną przed zatrzymaniem przez dowolną zatrzymującą się maszynę o n stanach uruchomioną na pustej taśmie. Dla każdego n maksimum istnieje, bo rozważamy skończenie wiele maszyn danego typu. Mimo to funkcji nie da się obliczać dla dowolnego n. Co więcej, jej wzrost ostatecznie przewyższa każdą funkcję obliczalną. Gdybyśmy mieli obliczalną górną granicę czasu zatrzymania takich maszyn, moglibyśmy uruchomić każdą odpowiednio długo i rozstrzygnąć, które nigdy się nie zatrzymają — a to dałoby rozwiązanie problemu stopu.

Maksimum nad zatrzymującymi się maszynami

Ustalamy konkretną konwencję maszyny Turinga, liczbę stanów n i alfabet. Istnieje tylko skończenie wiele maszyn o takiej wielkości. Część szybko się zatrzymuje, część po ogromnej liczbie kroków, część nigdy. Funkcja typu Busy Beaver wybiera rekord spośród tych, które ostatecznie się zatrzymują — np. największą liczbę wykonanych kroków albo największą liczbę zapisanych jedynek. Różne konwencje dają różne wartości, ale zachowują zasadniczą własność nieobliczalności.

Dlaczego wartość jest dobrze zdefiniowana

Może się wydawać paradoksalne, że nie potrafimy jej ogólnie obliczyć, choć maksimum istnieje. Dla ustalonego n zbiór rozważanych maszyn jest skończony, a podzbiór zatrzymujących się ma skończony zestaw czasów działania. Największy z nich istnieje. Problem nie polega więc na braku odpowiedzi matematycznej, lecz na braku algorytmu, który dla dowolnego n zawsze tę odpowiedź wyprodukuje.

Górna granica rozwiązałaby problem stopu

Załóżmy, że potrafimy obliczyć funkcję B(n) będącą górną granicą czasu wszystkich zatrzymujących się n-stanowych maszyn danego typu. Bierzemy konkretną taką maszynę i symulujemy ją przez B(n) kroków. Jeśli do tego czasu się nie zatrzymała, wiemy, że już nigdy tego nie zrobi. Otrzymalibyśmy metodę rozstrzygania zatrzymania dla tej klasy, a przez standardowe kodowania prowadzi to do sprzeczności z nierozstrzygalnością problemu stopu.

„Szybciej niż każda obliczalna”

Własność Busy Beaver jest mocniejsza niż stwierdzenie, że rośnie szybciej od wykładniczej, silni czy konkretnej funkcji Ackermanna. Dla dowolnej funkcji obliczalnej f istnieje dostatecznie duże n, od którego odpowiednia funkcja Busy Beaver przewyższa f w sensie dominacji opisanym w literaturze. Nie ma więc „jeszcze jednej sprytnej obliczalnej funkcji”, która dawałaby użyteczną ogólną górną granicę.

Granica między definicją i algorytmem

Busy Beaver pokazuje coś bardzo ważnego: prosta definicja matematyczna nie gwarantuje istnienia algorytmu do wyliczania jej wartości. Funkcja może być jednoznacznie określona i przyjmować skończoną wartość dla każdego n, a zarazem znajdować się poza zasięgiem ogólnego obliczenia. To jedna z najbardziej obrazowych konsekwencji nierozstrzygalności.

Dlaczego górne ograniczenia są tak trudne

Aby udowodnić, że Busy Beaver dla danego rozmiaru ma wartość co najwyżej M, nie wystarczy znaleźć bardzo długo działającą maszynę. Trzeba wykluczyć możliwość, że jakakolwiek inna maszyna tego rozmiaru zatrzymuje się jeszcze później. Dla każdej maszyny trzeba więc ostatecznie rozstrzygnąć: zatrzyma się czy będzie działać wiecznie. W małych przypadkach można to robić przez analizę i dowody, lecz wraz ze wzrostem liczby stanów problem coraz silniej splata się z problemem stopu. To dlatego dolne granice są stosunkowo naturalne — wystarczy skonstruować jednego „rekordzistę” — a pewna górna granica wymaga kontroli wszystkich kandydatów. Busy Beaver zamienia nierozstrzygalność w ekstremalny wyścig liczb.

Mały opis może definiować niewyobrażalną wartość

Busy Beaver jest szczególnie zaskakujący dlatego, że definicja funkcji jest krótka, a mimo to jej wartości ostatecznie wyprzedzają każdą funkcję obliczalną. Zwięzłość definicji nie oznacza więc łatwości wyznaczania wyników. To kolejny motyw teorii obliczalności: można jednoznacznie zdefiniować obiekt matematyczny, którego wartości nie dają się generować przez żaden algorytm dla wszystkich argumentów.

#Busy Beaver#ekstremalny wzrost#maszyna Turinga#nieobliczalność#problem stopu
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki