L'esempio di Dijkstra di un programma ambiguo

12

Saluti. Dijkstra ha scritto che anche poche righe di codice apparentemente semplice potrebbero essere irrimediabilmente ambigue. In almeno un lavoro, che non riesco a trovare ora per salvarmi la vita, ha dato un piccolo programma di esempio per dimostrare questa ambiguità. Qualcuno può indicarmi un suo foglio in cui include uno di questi esempi?

    
posta Dijkstra Reader 03.06.2011 - 20:09
fonte

2 risposte

11

Leggi questo:

link

Il link ha una buona copertura; cerca "problema di arresto"

Esistono diverse forme della fondamentale contraddizione di arresto.

def halts( code_block ):
    # Some magical code

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

Il "fischietto" fischia zero, una volta o un numero infinito di volte?

Se la funzione halts() determina che la funzione whistler sembra arrestarsi, la funzione whistler non può essere interrotta.

Se la funzione halts() determina che la funzione whistler non viene arrestata, la funzione whistler si interrompe.

Pertanto, la funzione halts() non può esistere.

    
risposta data 03.06.2011 - 20:35
fonte
2

Sei sicuro che il foglio fosse di Dijkstra? Reflections on Trusting Trust di Ken Thompson sembra che potrebbe essere stavi pensando. Dimostra come programmi assolutamente semplici, diretti e corretti potrebbero finire per fare qualcosa di assolutamente inaspettato che non è affatto visibile nella fonte. Anche se non è quello che stavi pensando, è un documento utile da leggere.

Se si va in una direzione diversa, se si vogliono esempi eccellenti di programmi brevi con comportamenti sorprendenti, il concorso C subdolo è grandioso. Ad esempio, guarda il il vincitore del 2008 . La sfida consisteva nel scrivere un programma a riga di comando per cancellare parte di un'immagine, in modo tale che l'immagine visivamente venisse cancellata perfettamente, ma il file conserva alcune informazioni sulla parte redatta dell'immagine. AND in modo tale che il tuo codice possa superare la revisione del codice. (Puoi scegliere il formato in cui è archiviata l'immagine.)

    
risposta data 04.06.2011 - 04:37
fonte

Leggi altre domande sui tag