Pozdrowienia Dijkstra napisał, że nawet kilka wierszy pozornie prostego kodu może być beznadziejnie niejednoznaczne. W co najmniej jednym dziele, którego nie mogę teraz znaleźć, aby uratować mi życie, podał mały przykładowy program, który ma wykazać tę dwuznaczność. Czy ktoś może wskazać mi jego artykuł, w którym zawiera jeden z tych przykładów?
Odpowiedzi:
Przeczytaj to:
http://en.wikipedia.org/wiki/Halting_problem#Recognizing_partial_solutions
http://www.cs.ucsb.edu/~pconrad/cs40/08S/notes/ ma ładny zasięg; wyszukaj „problem z zatrzymaniem”
Istnieje kilka form zasadniczej sprzeczności.
def halts( code_block ):
# Some magical code
def whistler():
while halts(whistler):
sys.whistle( 1 )
Czy „gwizdek” gwizdka zero, raz czy nieskończoną liczbę razy?
Jeśli halts()funkcja ustali, że funkcja whistlerwydaje się zatrzymywać, funkcja whistlernie może się zatrzymać.
Jeśli halts()funkcja stwierdzi, że funkcja whistlernie wydaje się zatrzymać, funkcja whistlerzatrzymuje się.
Dlatego halts()funkcja nie może istnieć.
Czy jesteś pewien, że papier napisał Dijkstra? Refleksje na temat Trusting Trust autorstwa Kena Thompsona brzmią tak, jakbyś mógł o tym myśleć. To pokazuje, jak absolutnie proste, proste i poprawne programy mogą skończyć, robiąc coś absolutnie nieoczekiwanego, co w ogóle nie jest widoczne w źródle. Nawet jeśli to nie to, o czym myślisz, warto przeczytać.
Idąc w innym kierunku, jeśli chcesz doskonałych przykładów krótkich programów o zaskakującym zachowaniu, podstępny konkurs C jest świetny. Na przykład spójrz na zwycięzcę z 2008 roku . Wyzwanie polegało na napisaniu programu wiersza polecenia, aby usunąć część obrazu w taki sposób, aby obraz był idealnie wygaszony, ale plik zachowuje pewne informacje o zredagowanej części obrazu. ORAZ w taki sposób, że Twój kod może przejść przegląd kodu. (Możesz wybrać format, w którym zdjęcie jest przechowywane.)
FILE_NOT_FOUND;)