Qual è un esempio di un problema aziendale computazionalmente impossibile?

Non tecnicamente impossibile, ma ...

Pianificazione delle risorse , con l'obiettivo di trovare il programma ideale che massimizza l'uso delle fasce orarie. Ero su un progetto una volta, nei miei primi giorni di calcolo, che aveva questo requisito. Ci ho lavorato un po 'prima che mi rendessi conto che era NP-difficile.

Altri esempi di problemi che non sono tecnicamente impossibili, ma tecnicamente difficili, possono essere trovati qui .

La maggior parte dei difficili problemi computazionali nell'informatica aziendale non sono impossibili, solo poco pratici. Il tuo amico ha ragione; puoi risolverne la maggior parte se butti abbastanza soldi a loro. Ma l'argomento è specioso; l'intero punto di gestione di un'attività è fare soldi, non perderlo.

Nella pratica quotidiana, parliamo della completezza di Turing in modo vago, non per dimostrare alcuni principi matematici, ma per illustrare (per esempio) l'inadeguatezza di HTML e CSS come un veicolo completo per la produzione di programmi completi di funzionalità.

Allo stesso modo, il problema dell'arresto è importante per i teorici, ma non ha molta rilevanza per la maggior parte delle aziende.

Altri hanno commentato questo, ma proverò a scrivere una risposta che dia il mio punto di vista.

Mi piace la risposta di Robert Harvey e i commenti alla sua risposta, e vorrei espandermi su quelli.

Penso che devi presentare questi problemi indecidibili (come la terminazione) in modo banale: ad esempio, uno strumento IDE che "controlla se questa funzione restituisce sempre un valore".

Durante l'insegnamento, il mio esempio preferito era il refactoring ( equivalenza della funzione, un altro problema indecidibile ). Ho chiesto:

how do you check if a function/program does the same after your nice refactoring? Sure, we have unit tests for that, but they do not cover all the cases. And they are boring to write... But we are programmers! We should write a program that checks if these two functions are producing always the same result! Why don't you try to write it?

o, come variante forse più vicina al tuo caso:

We have this legacy code written in an ancient obscure COBOL dialect, for which no spec and/or compiler exist. We only have the program. Our whole business relies on it, so we have to be 100% sure the new Java code does exactly the same in every situation. Management wants a program that do that, checking all possible cases, and estimates it can be done in 6 to 8 weeks. Why don't you try to write it?

Il punto non è scrivere un programma del genere. O una buona approssimazione dei requisiti. Il punto è rendersi conto che NON può essere fatto in modo diretto, NON sprecare innumerevoli nostri cercando di capire come farlo (solo per rendersi conto che non è possibile), ma riconoscerlo. "Ah, questo è indecidibile! Non è possibile farlo direttamente. Devo trovare un modo diverso, più intelligente per farlo, con una buona approssimazione".

Devi trovare un modo per presentare il problema in modo riconoscibile e apparentemente semplice. Non crederesti quanti studenti CS proveranno a scrivere subito un programma ... prima di prendere una classe di computabilità:)

Supponendo che potremmo mettere da parte le questioni morali per il momento:

L'azienda A ti ha contattato per un modo di comunicare tra gli uffici satellite A1 e A2 senza che nessuno oltre alle persone autorizzate in A1 e A2 sia in grado di comprendere la comunicazione.

L'azienda B ti ha contattato per un modo per intercettare in modo intelligente tutte le comunicazioni tra A1 e A2.

Ovviamente non puoi fare entrambe le cose.

A causa del modo in cui la matematica si risolve (la matematica esatta è stata sottoposta a ricerche continue per 100 anni), uno dei seguenti requisiti non può essere soddisfatto:

(1): Fornisci un algoritmo di crittografia che non può essere rotto da un utente malintenzionato con una quantità arbitraria di denaro disponibile.

(2): Fornire un algoritmo di interruzione della crittografia per un algoritmo di crittografia arbitrario che viene eseguito in un tempo ragionevole.

Recentemente ho preso una lezione su Business Process Model e Notation ( BPMN ). In questo modo si può facilmente notare che i flussi di lavoro con molte troppe parti, join e loop diventano rapidamente poco pratici (sebbene non necessariamente impossibile , AFAIK) da comprendere e controllare (quando si utilizzano troppe divisioni OR anziché XOR-split).

Per il settore del software, penso che lo stesso valga per problemi simili di "copertura di più condizioni" in analisi della copertura del codice .

Per un'azienda, la strada da seguire è quella di ridurre lo spazio del problema e non gettare più risorse al problema complesso. Nel mio esempio, aggiungi vincoli al flusso di lavoro, (o nell'analisi della copertura del codice, semplifica il codice), invece di lavorare sodo per trovare tutte, diciamo, N possibili tracce e risultati in cui N è un numero inimmaginabilmente grande.

A parte questo, penso che ci siano molti problemi nella rete / graph analisi che sono impossibili da risolvere (cercando di determinare una topologia di rete eseguendo iterativamente tutti i percorsi ecc.).

L'esempio classico sta provando a analizzare HTML con espressioni regolari . Questo può funzionare con set HTML limitati, ma una soluzione generale è impossibile, poiché hanno grammatiche diverse di Chomsky (come il link rende chiaro (ish)).

Più in generale ad alcune persone non piace pensare filosoficamente (come il tuo collega di lavoro) e non sono sicuro che tu possa argomentare la tua via d'uscita da una mentalità. Il suo primo punto è certamente sbagliato, ma il suo secondo potrebbe essere solo un modo per dire che non devo preoccuparmi di questo per codificare i moduli web per la ricezione delle merci. Ho una certa comprensione per questo, ma a volte conoscere la teoria significa che non ti impegni a trovare il Santo Graal in orario di lavoro.

Forse la risposta è che il tuo collega di lavoro è corretto. Forse hai frainteso Turing, o come si applica qui?

Tutte le macchine sono finite, quindi non ci sono macchine di Turing "reali" e nessun programma che non si fermerà mai. Un programma banale che esegue un ciclo infinito semplice potrebbe eseguire 5 minuti o 50 anni, ma su una macchina finita si fermerà. Anche un problema non banale di non interruzione come "calcolare più esattamente" si fermerà, perché alla fine il calcolo supererà la capacità di memorizzare ulteriori cifre.

Il risultato di Turing non garantisce nulla di particolarmente utile su macchine finite, quindi la tua ricerca è in definitiva infruttuosa. Meglio concentrarsi su quanto tempo e quanti soldi e lasciare infinito ai matematici.

Potresti pensare che un programma come { while true: print "running"; print "halted"; } sia un controesempio, ma non lo è. Questo programma ha effetti collaterali, che possono o meno causare l'arresto. Ignorando gli effetti collaterali, è possibile escogitare una prova formale che questo programma non si fermerà. In questa domanda ci occupiamo solo di programmi che eludono la prova formale di non fermarsi, dove la questione dell'arresto è indecidibile. Questo non è un programma del genere.

Può aiutare a distinguere Turing "strong" da Turing "debole". Le macchine di Turing forti sono in realtà infinite e se non riescono a fermarsi, funzioneranno per un tempo infinito. Non possiamo costruirli.

Le macchine di Turing debole hanno limiti finiti su tempo e spazio, e sono l'unico tipo che possiamo costruire. Siamo interessati a programmi che non possono essere fermati entro questi limiti. Turing ci dice che ci sono tali programmi ma non possiamo identificarli. Se i limiti sono abbastanza bassi, possiamo identificarli scrivendo il programma e portandolo ai suoi limiti.

L'essenza di Turing è che non ci sono scorciatoie. L'unico modo per essere certi che un problema sia computazionalmente fattibile è scrivere il programma, eseguirlo e scoprirlo. Con abbastanza tempo e denaro puoi scrivere tutti i programmi, eseguirli per sempre e nel tempo e trovare quelli che producono risultati (le cavezze). Gli altri continueranno a correre. Il tuo collaboratore ha abbastanza tempo e denaro per farlo?

Seriamente però, la disputa riguarda i limiti. Turing e NP ci dicono che determinate classi di problemi non possono essere risolti da computer all'interno di un dato budget o in un dato programma, indipendentemente da quanto sia grande il budget o quanto generoso possa essere quel programma. Esempi di questo tipo di problema abbondano: rompere le chiavi crittografiche; ottimizzare i percorsi per effettuare consegne a centinaia di indirizzi; scatole di imballaggio in camion; trovare bug in grandi programmi!

Quindi chiedi al tuo collega di lavoro un budget e un programma e prometti che puoi produrre un problema che non può essere risolto in quel budget o programma. Questa promessa sarà molto facile da mantenere.