L'exemple de Dijkstra d'un programme ambigu

12

Salutations. Dijkstra a écrit que même quelques lignes de code apparemment simple pouvaient être désespérément ambiguë. Dans au moins une œuvre que je ne trouve pas maintenant pour sauver ma vie, il a donné un petit exemple de programme pour démontrer cette ambiguïté. Quelqu'un peut-il m'indiquer un de ses papiers où il inclut l'un de ces exemples?

ambiguity Dijkstra Reader
la source

Réponses:

11

Lis ça:

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

http://www.cs.ucsb.edu/~pconrad/cs40/08S/notes/ a une bonne couverture; recherche de "problème d'arrêt"

Il existe plusieurs formes de la contradiction essentielle qui s’arrête.

def halts( code_block ):
    # Some magical code

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

Le "siffleur" siffle-t-il zéro, une fois ou un nombre infini de fois?

Si la halts()fonction détermine que la fonction whistlersemble s'arrêter, la fonction whistlerne peut pas s'arrêter.

Si la halts()fonction détermine que la fonction whistlerne semble pas s'arrêter, la fonction whistlers'arrête.

Par conséquent, la halts()fonction ne peut pas exister.

S.Lott
la source
4
Vous avez oublié la troisième option, où elle revient FILE_NOT_FOUND;)
FrustratedWithFormsDesigner
2
Merci! Ce que Dijkstra décrivait dans l'article que j'ai lu n'était cependant pas le problème de l'arrêt. Ce ne sont que quelques lignes de code simple, mais vous ne pouvez pas dire ce que cela signifie. Le contexte est que Dijkstra parle de méthodes qu'il utilise pour démontrer au public que la programmation est difficile, donc les programmeurs doivent être humbles. Notez que le papier n'est pas, je suis triste à dire, "The Humble Programmer". :)
Dijkstra Reader
Parlez -vous de cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD658.html ?
S.Lott
Merci encore. C'est triste à dire, ce n'est pas celui-là. Dans le document auquel je fais référence, Dijkstra dit spécifiquement que la programmation est difficile, même pour les gens intelligents, nous devons respecter cela, "Par exemple, que fait le petit programme suivant?"
Dijkstra Reader
Probablement pas cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html . Mais je le soulève comme une citation commune sur la difficulté de la programmation.
S.Lott
2

Êtes-vous sûr que le document a été rédigé par Dijkstra? Les réflexions sur Trusting Trust de Ken Thompson semblent être ce à quoi vous pensiez. Il montre comment des programmes absolument simples, directs et corrects peuvent finir par faire quelque chose d'absolument inattendu qui n'est pas du tout visible dans la source. Même si ce n'est pas ce à quoi vous pensiez, c'est un article intéressant à lire.

Dans une autre direction, si vous voulez d'excellents exemples de programmes courts avec un comportement surprenant, le concours C sournois est génial. Par exemple, regardez le gagnant de 2008 . Le défi consistait à écrire un programme en ligne de commande pour masquer une partie d'une image, de telle sorte que l'image soit parfaitement masquée visuellement, mais le fichier conserve certaines informations sur la partie caviardée de l'image. ET de telle manière que votre code puisse passer l'examen du code. (Vous pouvez choisir le format dans lequel l'image est stockée.)

btilly
la source
Je vous remercie! Oui, c'est certainement un document de Dijkstra auquel je fais référence.
Dijkstra Reader