Przykład niejednoznacznego programu Dijkstry

12

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?

Dijkstra Reader
źródło

Odpowiedzi:

11

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

S.Lott
źródło
4
Zapomniałeś trzeciej opcji, do której zwraca FILE_NOT_FOUND;)
FrustratedWithFormsDesigner
2
Dzięki! To, co Dijkstra opisywał w artykule, który przeczytałem, nie było jednak problemem zatrzymania. To tylko kilka wierszy prostego kodu, ale nie możesz powiedzieć, co to znaczy. Kontekst jest taki, że Dijkstra mówi o metodach, których używa, aby pokazać odbiorcom, że programowanie jest trudne, dlatego programiści muszą być pokorni. Zauważ, że gazeta nie jest, z przykrością mówię „Pokorny programista”. :)
Dijkstra Reader
Dzięki jeszcze raz. Przykro mi to mówić, to nie to. W artykule, o którym mówię, Dijkstra wyraźnie mówi, że programowanie jest trudne, nawet dla mądrych ludzi, musimy szanować, że: „Na przykład, co robi następujący mały program?”
Dijkstra Reader
Prawdopodobnie nie cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html . Ale podnoszę to jako powszechny cytat o tym, jak trudne jest programowanie.
S.Lott,
2

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

btilly
źródło
Dziękuję Ci! Tak, zdecydowanie mam na myśli artykuł Dijkstry.
Dijkstra Reader