Quando hai riscontrato l'arresto del problema sul campo? [chiuso]

Question

Quando ti sei mai imbattuto personalmente nel problema di arresto nel campo? Questo può accadere quando un collega / capo ha suggerito una soluzione che violerebbe i limiti fondamentali del calcolo o quando ti sei reso conto che un problema che stavi cercando di risolvere era, in effetti, impossibile da risolvere.

L'ultima volta che mi è venuta in mente è stato quando studiavo gli ispettori. La nostra classe ha capito che sarebbe impossibile scrivere un perfetto correttore di tipi (uno che accetterebbe tutti i programmi che verrebbero eseguiti senza errori di tipo, e respingere tutti i programmi che verrebbero eseguiti con errori di tipo) perché questo, di fatto, risolverebbe il problema dell'arresto . Un altro è stato quando ci siamo resi conto, nella stessa classe, che sarebbe impossibile determinare se una divisione si sarebbe mai verificata per zero, nella fase di controllo del tipo, perché controllare se un numero, in fase di esecuzione, è zero, è anche una versione del problema di arresto.

Answer 1

I letteralmente mi hanno assegnato il problema di arresto, come in "scrivere un plug-in di monitoraggio per determinare se un host è permanentemente inattivo". Sul serio? OK, quindi darò solo una soglia. " No, perché potrebbe tornare in seguito. "

Ne è seguita molta esposizione teorica.

Answer 2

Anni fa, ricordo di aver letto una recensione (nella rivista Byte, credo) di un prodotto chiamato Basic Infinite Loop Finder o BILF. BILF avrebbe dovuto scansionare il codice sorgente di Microsoft Basic e trovare eventuali loop che non fossero terminati. Ha affermato di essere in grado di trovare qualsiasi loop infinito nel codice.

Il revisore è stato abbastanza esperto da sottolineare che, affinché quel programma funzionasse in tutti i casi, avrebbe dovuto risolvere il problema di arresto e sarebbe arrivato al punto di fornire una prova matematica del perché non poteva funzionare in tutti i casi.

Nel prossimo numero, hanno pubblicato una lettera di un rappresentante dell'azienda che spiegava che il problema sarebbe stato risolto nella prossima versione.

Aggiornamento: mi sono imbattuto in un'immagine dell'articolo su imgur. Mi sono ricordato della rivista sbagliata. Era il calcolo creativo, non il byte. Altrimenti, è praticamente come me lo ricordavo.

Puoi vederne una versione in alta risoluzione su imgur .

Answer 3

Il progetto a cui sto lavorando in questo momento ha problemi indecidibili dappertutto. È un generatore di unit test, quindi in generale ciò che cerca di realizzare è rispondere alla domanda "cosa fa questo programma" . Che è un'istanza di un problema di arresto. Un altro problema che si è presentato durante lo sviluppo è " sono date due funzioni (test) uguali " ? O anche " importa l'ordine di quelle due chiamate (asserzioni) " ?

La cosa interessante di questo progetto è che, anche se non puoi rispondere a queste domande in tutte , puoi trovare soluzioni intelligenti che risolvano il problema del 90% di il tempo, che per questo dominio è in realtà molto buono.

Altri strumenti che tentano di ragionare su altri codici, come l'ottimizzazione di compilatori / interpreti, strumenti di analisi del codice statico, persino strumenti di refactoring, rischiano di colpire (quindi essere costretti a trovare soluzioni alternative) al problema di arresto.

Answer 4

Esempio 1. Quante pagine nella mia segnalazione?

Quando stavo imparando a programmare, ho giocato con uno strumento per stampare graziosi report dai dati. Ovviamente volevo che fosse davvero flessibile e potente, quindi sarebbe il generatore di report a terminare tutti i generatori di report.

La definizione del rapporto è risultata così flessibile da essere Turing completa. Potrebbe guardare le variabili, scegliere tra le alternative, usare i loop per ripetere le cose.

Ho definito una variabile incorporata N, il numero di pagine nell'istanza del rapporto, in modo da poter inserire una stringa che dicesse "pagina n di N". su ogni pagina. Ho fatto due passaggi, il primo per contare le pagine (durante le quali N è stato impostato su zero) e il secondo per generarle effettivamente, utilizzando la N ottenuta dal primo passaggio.

A volte il primo passaggio calcolava N, quindi il secondo passaggio generava un numero diverso di pagine (perché ora la N diversa da zero cambiava ciò che faceva il rapporto). Ho provato a fare passaggi in modo iterativo finché la N non si è stabilita. Poi ho capito che questo era senza speranza perché se non si fosse sistemato?

Questo porta quindi alla domanda "Posso almeno rilevare e avvisare l'utente se l'iterazione non si accontenterà mai di un valore stabile per il numero di pagine prodotte dal loro rapporto?" Fortunatamente a questo punto mi ero interessato a leggere su Turing, Godel, la computabilità ecc. E ho fatto il collegamento.

Anni dopo ho notato che a volte MS Access stampa "Pagina 6 di 5", il che è una cosa davvero meravigliosa.

Esempio 2: compilatori C ++

Il processo di compilazione prevede l'espansione dei modelli. Le definizioni dei modelli possono essere selezionate da più specializzazioni (abbastanza buone da fungere da "cond") e possono anche essere ricorsive. Quindi è un meta-sistema completo (puramente funzionale) di Turing, in cui le definizioni dei template sono il linguaggio, i tipi sono i valori e il compilatore è davvero un interprete. Questo è stato un incidente.

Di conseguenza non è possibile esaminare un determinato programma C ++ e dire se il compilatore potrebbe in linea di principio terminare con una compilazione riuscita del programma.

I venditori di compilatori riescono a risolvere questo problema limitando la profondità dello stack del modello ricorsivo. È possibile regolare la profondità in g ++.

Answer 5

Molte lune fa stavo assistendo un consulente per la nostra azienda che stava implementando un sistema ferroviario molto complesso per spostare cestini di parti metalliche dentro e fuori da un altoforno di 1500 gradi. La pista stessa era un "mini-railyard" piuttosto complesso sul piano del negozio che si intersecava in un paio di punti. Numerosi pallet motorizzati trasporterebbero cestini di pezzi secondo un programma. Era molto importante che le porte della fornace fossero aperte il più breve tempo possibile.

Poiché l'impianto era in piena produzione, il consulente non era in grado di eseguire il suo software in "tempo reale" per testare i suoi algoritmi di pianificazione. Invece, ha scritto un grazioso simulatore grafico. Mentre guardavamo i pallet virtuali muoversi sul suo layout di traccia sullo schermo, ho chiesto a "come farai a sapere se hai dei conflitti di programmazione?" & Quot;

La sua risposta rapida, " Facile - la simulazione non si fermerà mai. "

Answer 6

L'analisi sofisticata del codice statico può incorrere nel problema di arresto.

Ad esempio, se una macchina virtuale Java è in grado di dimostrare che un pezzo di codice non accederà mai a un indice di array fuori limite, può omettere tale controllo ed eseguire più velocemente. Per alcuni codici questo è possibile; man mano che diventa più complesso diventa il problema di arresto.

Answer 7

Questo è ancora un problema per gli shader nelle applicazioni GPU. Se uno shader ha un ciclo infinito (o un calcolo molto lungo), il driver (dopo un certo limite di tempo) dovrebbe fermarlo, uccidere il frammento o lasciarlo funzionare? Per i giochi e altre cose commerciali, il primo è probabilmente quello che vuoi, ma per il calcolo scientifico / GPU, il secondo è quello che vuoi. Peggio ancora, alcune versioni di Windows presumono che dato che il driver grafico non risponde da tempo, lo uccide, il che limita artificialmente la potenza di calcolo quando si esegue il calcolo sulla GPU.

Non esiste un'API per un'applicazione per controllare come dovrebbe comportarsi il driver o impostare il timeout o qualcosa del genere, e certamente non c'è modo per il driver di dire se lo shader sta per finire o meno.

Non so se questa situazione è migliorata di recente, ma mi piacerebbe saperlo.

Answer 8

Un'altra versione comune di questo è " dobbiamo eliminare eventuali deadlock nel nostro codice multi-thread " ;. Una richiesta perfettamente ragionevole, dal punto di vista della gestione, ma per evitare deadlock nel caso generale, è necessario analizzare ogni possibile stato di blocco in cui il software può entrare, il che non sorprende, equivalente al problema di arresto.

Ci sono modi per "risolvere" parzialmente " deadlock in un sistema complesso imponendo un altro livello sopra il blocco (come un ordine di acquisizione definito), ma questi metodi non sono sempre applicabili.

---

Perché questo equivale al problema di arresto:

Immagina di avere due blocchi, A e B e due thread, X e Y. Se il thread X ha il blocco A, e vuole anche il blocco B, e il thread Y ha il blocco B e vuole anche A, allora hai un deadlock .

Se sia X che Y hanno accesso sia ad A che a B, l'unico modo per assicurarsi di non entrare mai nello stato cattivo è determinare tutti i possibili percorsi che ogni thread può percorrere attraverso il codice e l'ordine in cui possono acquisire e conservare i blocchi in tutti questi casi. Quindi si determina se i due thread possono mai acquisire più di un blocco in un ordine diverso.

Ma, determinare tutti i possibili percorsi che ogni thread può seguire attraverso il codice è (nel caso generale) equivalente al problema di arresto.

Answer 9

Il sistema di test di Perl mantiene un contatore di test. O metti il ??numero di test che eseguirai nella parte superiore del programma o dichiari che non lo seguirai. Questa guardia contro il tuo test è uscita prematuramente, ma ci sono altre guardie quindi non è poi così importante.

Di tanto in tanto qualcuno cerca di scrivere un programma per contare il numero di test per te. Questo è, ovviamente, sconfitto da un semplice ciclo. Avanzano comunque, facendo trucchi sempre più elaborati per cercare di rilevare loop e indovinare quante iterazioni ci saranno e risolvere il problema di arresto. Di solito dichiarano che deve solo essere "abbastanza buono".

Ecco un esempio particolarmente elaborato.

Answer 10

Una volta stavo lavorando a un progetto di integrazione nel dominio ATM (Automated Teller Machines). Il cliente mi ha chiesto di generare un rapporto dal mio sistema per le transazioni inviate dal cambio paese che non sono state ricevute dal mio sistema !!

Answer 11

Ho trovato un documento Berkeley: Looper: rilevamento leggero di cicli infiniti in fase di esecuzione http://www.eecs.berkeley.edu/~jburnim/pubs /BurnimJalbertStergiouSen-ASE09.pdf

LOOPER può essere utile poiché la maggior parte dei loop infiniti sono errori banali. Tuttavia, questo documento non menziona nemmeno il problema dell'arresto!

Cosa dicono delle loro limitazioni?

  

[LOOPER] in genere non può ragionare su loop in cui la non terminazione   dipende dai dettagli della mutazione dell'heap in ogni iterazione del ciclo.   Questo perché la nostra esecuzione simbolica è conservativa   concretizzare i suggerimenti e il nostro ragionamento simbolico insufficientemente   potente. Crediamo che combinando le nostre tecniche con l'analisi della forma   e la generazione e la prova invarianti più potenti sarebbero preziose   lavori futuri.

In altre parole, il problema verrà risolto nella prossima versione di " ;.

Answer 12

Dal Panoramica funzionale di (Eclipse) Visual Editor :

  

Può essere l'Eclipse Visual Editor (VE)   utilizzato per aprire qualsiasi file .java. Allora   analizza il codice sorgente Java cercando   per fagioli visivi. ...

     

Solo alcuni strumenti di modifica visiva   fornire un modello visivo di codice che   quel particolare strumento visivo stesso ha   generato. Modifica diretta successiva   del codice sorgente può impedire il   strumento visivo dall'analisi del codice e   costruire un modello.

     

Eclipse VE, tuttavia, ... può essere   utilizzato per modificare le GUI da zero o   dai file Java che sono stati   'hardcoded' o integrato in un altro   strumento visivo. Il file sorgente può   o essere aggiornato utilizzando il grafico   Visualizzatore, albero o proprietà di JavaBeans   visualizza oppure può essere modificato direttamente da   l'editor di sorgenti.

Forse dovrei restare con Matisse per ora.

Non correlato, ecco qualcuno che chiede il problema dell'arresto all'interno di Eclipse.

Ad essere onesti, il dominio di VE è piuttosto limitato e probabilmente non impazzirà per cose difficili come la riflessione. Tuttavia, l'affermazione di creare una GUI da qualsiasi file java sembra fermarsi.

Answer 13

" Come puoi assicurarmi che il tuo codice sia privo di bug al 100%? "