Dijkstras Beispiel für ein mehrdeutiges Programm

12

Anreden. Dijkstra schrieb, dass selbst einige Zeilen scheinbar einfachen Codes hoffnungslos mehrdeutig sein könnten. In mindestens einem Werk, das ich jetzt nicht finden kann, um mein Leben zu retten, gab er ein kleines Beispielprogramm, um diese Mehrdeutigkeit zu demonstrieren. Kann mich jemand auf ein Papier von ihm verweisen, in dem er eines dieser Beispiele anführt?

ambiguity Dijkstra Reader
quelle

Antworten:

11

Lesen Sie dies:

http://en.wikipedia.org/wiki/Halting_problem#Recognizing_partial_solutions

http://www.cs.ucsb.edu/~pconrad/cs40/08S/notes/ hat eine gute Abdeckung; Suche nach "halting problem"

Es gibt verschiedene Formen des wesentlichen Widerspruchs.

def halts( code_block ):
    # Some magical code

def whistler():
    while halts(whistler): 
        sys.whistle( 1 )

Pfeift der "Pfeifer" einmal oder unendlich oft auf Null?

Wenn die halts()Funktion feststellt, dass die Funktion whistleranzuhalten scheint, kann die Funktion whistlernicht angehalten werden.

Wenn die halts()Funktion feststellt, dass die Funktion whistlernicht angehalten erscheint, wird die Funktion whistlerangehalten.

Daher kann die halts()Funktion nicht existieren.

S.Lott
quelle
4
Sie haben die dritte Option vergessen, bei der sie zurückkehrt FILE_NOT_FOUND;)
FrustratedWithFormsDesigner
2
Vielen Dank! Was Dijkstra in der Zeitung beschrieb, die ich las, war jedoch nicht das Problem des Stillstands. Es sind nur ein paar Zeilen einfachen Codes, aber Sie können nicht sagen, was das bedeutet. Der Kontext ist, dass Dijkstra über Methoden spricht, die er verwendet, um dem Publikum zu demonstrieren, dass das Programmieren schwierig ist, daher müssen Programmierer bescheiden sein. Beachten Sie, dass es sich bei dem Papier nicht um "The Humble Programmer" handelt. :)
Dijkstra Reader
Sprechen Sie über cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD658.html ?
S.Lott
Danke noch einmal. Traurig zu sagen, das ist nicht der eine. In dem Artikel, auf den ich mich beziehe, sagt Dijkstra ausdrücklich, dass das Programmieren selbst für kluge Leute schwierig ist. Wir müssen das respektieren: "Was macht zum Beispiel das folgende kleine Programm?"
Dijkstra Reader
Wahrscheinlich nicht cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html . Aber ich nehme es als ein allgemeines Zitat darüber, wie schwer das Programmieren ist.
S.Lott
2

Sind Sie sicher, dass das Papier von Dijkstra war? Überlegungen zu Trusting Trust von Ken Thompson scheinen das zu sein, woran Sie gedacht haben. Es zeigt, wie absolut einfache, unkomplizierte und korrekte Programme etwas absolut Unerwartetes tun können, das in der Quelle überhaupt nicht sichtbar ist. Auch wenn es nicht das ist, woran Sie gedacht haben, ist es eine lohnende Zeitung zum Lesen.

Wenn Sie in eine andere Richtung gehen und hervorragende Beispiele für Kurzprogramme mit überraschendem Verhalten suchen, ist der hinterhältige C-Wettbewerb großartig. Schauen Sie sich zum Beispiel den Gewinner 2008 an . Die Herausforderung bestand darin, ein Befehlszeilenprogramm zu schreiben, um einen Teil eines Bildes so auszublenden, dass das Bild optisch perfekt ausgeblendet wurde, die Datei jedoch einige Informationen über den redigierten Teil des Bildes enthält. UND so, dass Ihr Code die Codeüberprüfung bestehen kann. (Sie können das Format auswählen, in dem das Bild gespeichert wird.)

btilly
quelle
Vielen Dank! Ja, es ist definitiv ein Artikel von Dijkstra, auf den ich mich beziehe.
Dijkstra Reader