Nie da się zbudować uniwersalnego testera wszystkich niebanalnych zachowań programów
Twierdzenie Rice’a rozszerza intuicję problemu stopu. Dla programów o mocy maszyny Turinga każda nietrywialna własność semantyczna obliczanej funkcji lub rozpoznawanego języka jest nierozstrzygalna w pełnej ogólności. „Semantyczna” oznacza, że pytamy o to, co program robi, a nie jak wygląda jego kod; „nietrywialna” — że własność ma przynajmniej jeden program, który ją posiada, i przynajmniej jeden, który jej nie posiada. Dlatego nie istnieje doskonały analizator odpowiadający dla dowolnego programu na pytania typu „czy zawsze zwraca zero?” albo „czy oblicza dokładnie tę funkcję?”. Narzędzia praktyczne działają dzięki ograniczeniom i aproksymacji.
Kod a znaczenie programu
Własności syntaktyczne można często sprawdzać bez problemu: czy kod zawiera określoną instrukcję, ile ma funkcji, czy parser zaakceptuje składnię. Twierdzenie Rice’a dotyczy własności semantycznych, czyli zależnych wyłącznie od zachowania obliczenia. Dwa programy napisane zupełnie inaczej, ale obliczające tę samą funkcję, muszą być traktowane identycznie przez taką własność.
Nietrywialność jest kluczowa
Własność „program oblicza jakąś częściowo obliczalną funkcję” byłaby trywialna w rozważanym modelu, bo spełniają ją wszystkie programy. Interesujące pytania rozdzielają programy na co najmniej dwie grupy: takie, które mają daną cechę, i takie, które jej nie mają. Klasyczne sformułowania twierdzenia Rice’a mówią, że nie da się ogólnie rozstrzygać takich nietrywialnych własności indeksów programów, jeśli zależą tylko od ich semantyki.
Przykłady, które wpadają w barierę
Możemy pytać, czy program zawsze zwraca wynik, czy oblicza funkcję stałą zero, czy akceptuje dokładnie określony język albo czy jego dziedzina ma pewną własność. Dla pełnego modelu obliczeń wiele takich pytań jest nierozstrzygalnych. To znacznie szerszy obraz niż pojedynczy problem stopu: bariera obejmuje całą rodzinę automatycznych analiz zachowania.
Czego twierdzenie nie zabrania
Rice nie mówi, że analiza programów jest bezsensowna. Możemy rozstrzygać własności dla ograniczonych języków, analizować przybliżenia, wymagać adnotacji i dowodów albo zwracać odpowiedź tylko wtedy, gdy narzędzie potrafi ją uzasadnić. Weryfikator może być dźwięczny, lecz niezupełny: nigdy nie zaakceptuje błędnego programu, ale czasem odmówi rozstrzygnięcia poprawnego. To typowa cena za ominięcie bariery pełnej ogólności.
Dlaczego to ma znaczenie dla narzędzi programistycznych
Marzenie o analizatorze, który bierze dowolny program i zawsze bezbłędnie rozstrzyga wszystkie interesujące własności zachowania, jest matematycznie niemożliwe. Projektanci kompilatorów, verifierów i analizatorów statycznych muszą więc świadomie wybierać kompromis: zakres języka, rodzaj własności, dokładność albo gwarancję zakończenia. Ograniczenie wynika z teorii obliczalności, a nie z niedojrzałości narzędzi.
Rice dotyczy semantyki, nie każdego pytania o kod
Twierdzenie Rice’a nie mówi, że o programach nie da się automatycznie ustalić niczego. Własności czysto syntaktyczne — liczba znaków, użycie konkretnej instrukcji, poprawność gramatyczna — można często sprawdzać mechanicznie. Bariera pojawia się dla nietrywialnych własności semantycznych funkcji obliczanej przez program, czyli takich, które zależą od tego, co program robi, a nie jak zapisano jego kod. „Czy ten program oblicza zawsze zero?” albo „czy akceptuje jakieś wejście?” należą do innego rodzaju pytań niż „czy zawiera pętlę for”. To rozróżnienie wyjaśnia, dlaczego praktyczne analizatory kodu mogą świetnie wykonywać wiele użytecznych kontroli, a mimo to nie istnieje idealny analizator wszystkich możliwych zachowań.
„Nietrywialna” ma techniczne znaczenie
W twierdzeniu Rice’a własność jest nietrywialna, jeśli ma ją przynajmniej jedna obliczalna funkcja i przynajmniej jedna jej nie ma. Własności prawdziwe dla wszystkich programów albo dla żadnego nie wymagają analizy zachowania i są trywialnie rozstrzygalne. To drobne zastrzeżenie jest ważne: twierdzenie nie zakazuje automatycznego odpowiadania na każde pytanie semantyczne, lecz obejmuje właśnie te rozróżnienia zachowania, które naprawdę dzielą programy na co najmniej dwie klasy.