Zakłopotany twierdzeniem Rice'a


37

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!nn

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

  • 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.σ

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?


8
„Zgodnie z twierdzeniem Rice'a wszystko jest niemożliwe”. -- Nie. „Każda właściwość programu komputerowego jest niepoliczalna”. -- Nie. Jednak nie jesteś sam: większość uczniów napotyka to nieporozumienie.
Raphael

Odpowiedzi:


36

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 )fasolnfa(n)sol(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ą.fP.fasolP.

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).nm
  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.σσσ

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ą.


Nie mogę uzyskać tej odpowiedzi .. (Przepraszam, jeśli pytam o to samo, ale dobrze byłoby wyjaśnić ten punkt). Mówi, że możesz modyfikować te programy, zmieniając ich składnię, aby uzyskać równoważnik ekstensywny , ale jak sprawdzić, czy są one równoważne ekstensywnie? Nie można używać programu do porównywania, jeśli funkcje tych programów mają ogólnie obie te właściwości, więc kiedy mówimy „modyfikuj”, myślę, że jest to możliwe, ponieważ są to proste przykłady (czy dodałbyś „modyfikuj ostrożnie”? IDE dla tego?? ..) Myślę, że raz zmodyfikowany, nie możesz ogólnie sprawdzić, więc być może Rice trzyma.
Hernan_eche

1
Zasadniczo sprawdza się, czy dwa konkretne programy są zasadniczo równe, udowadniając, że tak jest. Czy sprzeciwiasz się temu, że dla wszystkich liczb całkowitych, nawet jeśli komputer nie może „sprawdzić” tej równości dla wszystkich wartości? Mam nadzieję, że nie. Istnieje różnica między pisaniem programu, który oblicza wartość logiczną, a dowodzeniem, że pewne stwierdzenie ma pewną wartość prawdy. Są rzeczy, które możemy udowodnić, ale nie możemy ich obliczyć (np. Fakt, że dwa konkretne programy są w zasadzie równe lub że dodanie jest przemienne). n+m=m+n
Andrej Bauer,

Ponadto w swoim rozumowaniu dokonujesz dziwnego skoku rozumowania: skoro równość zewnętrzna nie jest rozstrzygalna, twierdzenie Rice'a może być fałszywe. Jak to? I tylko dlatego, że równość ekstensywna jest nierozstrzygalna, nie oznacza to, że nie ma żadnych jej przypadków, o których moglibyśmy zdecydować. Te, o których wspomniałem - możemy o nich decydować.
Andrej Bauer,

36

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ę zestawP.Rmi

{M.faM.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 .


1
Zgubiłem się po około pierwszym zdaniu. Przepraszam. Czy ktoś może wyjaśnić różnicę między właściwością semantyczną a składniową?
MathematicalOrchid

@MathematicalOrchid: Możesz bezpiecznie zignorować to zdanie; pierwszy akapit zawiera wszystkie potrzebne informacje. Zresztą i tak opracuję.
Raphael

2
Semantyczny = o tym, co robi program. Składnia = o tym, jak wygląda program.
reinierpost
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.