Zakłopotany twierdzeniem Rice'a

Podsumowanie: Zgodnie z twierdzeniem Rice'a wszystko jest niemożliwe. A jednak cały czas robię to , jak się wydaje, rzeczy niemożliwe !

Oczywiście twierdzenie Rice'a nie mówi po prostu „wszystko jest niemożliwe”. Mówi coś bardziej szczegółowego: „Każda właściwość programu komputerowego jest niepoliczalna”.

(Jeśli chcesz podzielić włosy, każdą właściwość „nietrywialną”. To znaczy właściwości, które posiadają wszystkie programy lub które nie posiadają żadnych programów, można w prosty sposób obliczyć. Ale żadnej innej właściwości nie można obliczyć.)

Właśnie to twierdzenie mówi lub wydaje się mówić. I przypuszczalnie duża liczba bardzo inteligentnych ludzi dokładnie zweryfikowała poprawność tego twierdzenia. Ale wydaje się całkowicie przeciwstawić logice! Istnieje wiele właściwości programów, których obliczenia są trywialne !! Na przykład:

• Ile kroków wykonuje program przed zatrzymaniem? Decyzja, czy liczba ta jest skończona czy nieskończona, jest właśnie problemem zatrzymania, którego nie można obliczyć. Decyzja, czy liczba ta jest większa czy mniejsza niż jakieś skończone jest banalna! Wystarczy uruchomić program na maksymalnie kroków i sprawdzić, czy się zatrzyma, czy nie. Łatwy!$n$$n$

• Podobnie, czy program wykorzystuje więcej lub mniej niż jednostek pamięci w pierwszych krokach wykonania? Trywialnie obliczalne.$n$$m$

• Czy tekst programu wspomina o zmiennej o nazwie ? Trywialna analiza tekstowa ujawni odpowiedź.$k$

• Czy program wywołuje polecenie ? Ponownie zeskanuj tekst programu w poszukiwaniu nazwy tego polecenia.$\sigma$

Widzę wiele właściwości, które również wyglądają na nieobliczalne; np. ile dodatków wykonuje pełne uruchomienie programu? Cóż, to prawie tak samo, jak pytanie, ile kroków wykonuje program, co jest praktycznie problemem zatrzymania. Ale wygląda na to, że istnieje mnóstwo właściwości programu, które naprawdę, bardzo łatwo jest obliczyć. A jednak twierdzenie Rice'a twierdzi, że żadnego z nich nie da się obliczyć.

Czego tu brakuje?

Na potrzeby tej dyskusji „program” jest fragmentem kodu, który zawsze przyjmuje liczbę całkowitą jako dane wejściowe i albo działa wiecznie, albo zwraca liczbę całkowitą. Mówimy, że dwa programy i są extensionally równać , jeśli obliczyć tę samą funkcję, czyli dla każdej liczby albo zarówno i prowadzony na zawsze, albo oboje kończą i wyjście tego samego numeru.g n f ( n ) g ( n $f$$g$$n$$f(n)$$g(n)$

Ekstensjonalny nieruchomość programów jest własność , który szanuje ekstensjonalny równość, czyli jeśli i są extensionally równe wtedy albo obie mają własność lub oba nie mają.$P$$f$$g$$P$

Oto kilka przykładów właściwości innych niż wymiarowe:

1. Program zatrzymuje się w ciągu kroków. (Zawsze możemy zmodyfikować program do rozszerzenia równego, który działa dłużej).$n$
2. Program wykorzystuje mniej niż komórek pamięci w pierwszych krokach wykonania. (Zawsze możemy zmodyfikować program do rozszerzenia równego, aby zużywał trochę pamięci bez wyraźnego powodu).$n$$m$
3. Tekst programu wspomina o zmiennej o nazwie k. (Możemy zmieniać nazwy zmiennych).
4. Czy program wywołuje polecenie . Może to trochę zależeć od tego, czym jest , ale jeśli jest to coś, co można w jakiś sposób zasymulować, możemy uniknąć i nadal mieć program, który jest zasadniczo równy oryginalnemu.$\sigma$$\sigma$$\sigma$

Jestem pewien, że zauważyłeś, że dokładnie wymieniałem twoje rzekome kontrprzykłady na twierdzenie Rice'a:

Twierdzenie (Rice): Obliczalna ekstensywna właściwość programów zawiera wszystkie programy lub żadnego.

Istnieje inny sposób na wyjaśnienie tego: musisz odróżnić program od funkcji, którą oblicza. Wiele różnych programów oblicza tę samą funkcję (wszystkie są na ogół równe). Twierdzenie Rice'a dotyczy właściwości funkcji, a nie właściwości programów, które je obliczają.

Podstawowe nieporozumienie:

Każda właściwość programu komputerowego jest niepoliczalna

Nie o tym mówi twierdzenie Rice'a. Mówi o właściwościach funkcji i że zestaw programów obliczających tę funkcję nie jest rozstrzygalny. Formalnie, biorąc pod uwagę zestaw$\emptyset \subset P \subset \mathsf{RE}$

$\qquad \displaystyle \{ \langle M \rangle \mid f_M \in P \}$

nie podlega rozstrzygnięciu. Dla wymienionych właściwości nie znajdziesz odpowiedniego dla którego zestaw programów ma ten formularz. Niektóre programy dla jednej funkcji mogą mieć właściwość, podczas gdy inne (dla tej samej funkcji) mogą nie mieć. Zobacz tutaj kilka przykładów.$P$

Twierdzenie Rice'a dotyczy właściwości semantycznych (właściwości funkcji obliczonej przez program, np. Dziedziny lub zakresu wartości). To, o czym mówisz, to właściwości składniowe (właściwości programu , takie jak środowisko wykonawcze lub liczba używanych zmiennych).

Wydaje się, że niewiele wiadomo na temat właściwości składniowych; zobacz to pytanie .