Quel est un exemple d'un problème commercial impossible à calculer?

17

J'ai un collègue qui refuse d'accepter la réalité que les machines Turing (et les machines Von Neuman par extension) ne peuvent pas résoudre leur propre problème d'arrêt en déclarant:

Vous pouvez tout faire avec suffisamment de temps et d'argent.

Il n'aime pas non plus les problèmes théoriques faisant valoir que:

Dans notre domaine, nous ne rencontrerons jamais ces questions. Nous sommes des développeurs d'applications, pas des scientifiques théoriques.

Existe-t-il un bon exemple de problème commercial impossible sur le plan informatique que je pourrais utiliser pour l'aider à le convaincre?

Jesan Fafon
la source
11
Vous ne pouvez pas démontrer par l'exemple que quelque chose est impossible. Votre collègue dira simplement: "Cela ne fonctionne pas parce que nous n'avons pas trouvé la bonne approche". Le mieux que vous puissiez faire est de lui montrer une preuve. S'il ne l'achète pas, il est soit vraiment stupide, soit un crétin ou les deux. Voici une liste de problèmes indécidables: en.wikipedia.org/wiki/List_of_undecidable_problems
Thomas Eding
18
On a dit à un théoricien et à un ingénieur qu'ils pouvaient embrasser une fille en parcourant à plusieurs reprises la distance entre eux et elle de moitié. Le théoricien a immédiatement renoncé à dire "c'est impossible, je n'y arriverai jamais". L'ingénieur s'y est mis, disant "je vais m'approcher suffisamment pour des raisons pratiques". Vous, monsieur, devez essayer ce baiser.
gbjbaanb
2
@gbjbaanb: C'est un bon descripteur de nombreuses solutions non optimales aux problèmes NP-difficiles, et savoir que ces problèmes sont (pratiquement) impossibles à résoudre classiquement est la raison pour laquelle vous optez pour la méthode alternative. Si vous n'acceptez pas que certains problèmes soient pratiquement ou littéralement impossibles à résoudre, vous ne chercherez pas de solutions imparfaites qui pourraient donner une réponse "assez bonne" après une période indéterminée.
Phoshi
3
@Phoshi non, le fait est que les solutions d'ingénierie du monde réel ne nécessitent qu'une solution suffisamment bonne pour résoudre le problème suffisamment pour être acceptée. Le résoudre parfaitement ne vaut pas le temps et les dépenses. par exemple. Le problème du voyageur de commerce est impossible étant donné plus de quelques nœuds, mais une solution moins qu'optimale est toujours requise (et livrée) par de nombreuses entreprises. Si nous ne produisions que la perfection, personne n'en aurait.
gbjbaanb
10
@gbjbaanb: C'est vrai, mais la seule raison pour laquelle ils ont résolu ces problèmes est en acceptant d'abord que vous ne pouvez pas "faire quoi que ce soit avec suffisamment de temps et d'argent" et en cessant de rechercher la solution optimale. La connaissance de ce que vous ne pouvez pas faire est souvent tout aussi importante pour trouver une solution que la connaissance de ce que vous pouvez faire.
Phoshi

Réponses:

11

Pas techniquement impossible, mais ...

Planification des ressources , dans le but de trouver le calendrier idéal qui maximise l'utilisation des plages horaires. J'étais sur un projet une fois, dans mes premiers jours informatiques, qui avait cette exigence. J'y ai travaillé un certain temps avant de réaliser que c'était NP-difficile.

D'autres exemples de problèmes qui ne sont pas techniquement impossibles, mais qui sont techniquement difficiles, peuvent être trouvés ici .

La plupart des problèmes de calcul difficiles dans l'informatique d'entreprise ne sont pas impossibles, mais peu pratiques. Votre ami a raison; vous pouvez résoudre la plupart d'entre eux si vous leur jetez suffisamment d'argent. Mais l'argument est spécieux; tout l'intérêt de gérer une entreprise est de gagner de l'argent, pas de le perdre.

Dans la pratique quotidienne, nous parlons de l'intégralité de Turing d'une manière vague, non pas pour démontrer un principe mathématique, mais pour illustrer (par exemple) l'insuffisance de HTML et CSS en tant que véhicule complet pour produire des programmes complets.

De même, le problème de l'arrêt est important pour les théoriciens, mais il n'a pas beaucoup de pertinence pour la plupart des entreprises.

Robert Harvey
la source
14
Le problème d'arrêt apparaît dans l'analyse statique du code. De cela, vous pouvez obtenir des problèmes banals comme "voici du code, faites en sorte qu'il soit joli" à "voici du code, est-ce un malware" - le premier est important pour les entreprises qui fabriquent des IDE (coloration syntaxique, refactoring), le second pour sociétés antivirus et professionnels de la sécurité.
12
"De même, le problème de l'arrêt est important pour les théoriciens, mais il n'a pas beaucoup de pertinence pour la plupart des entreprises.": Eh bien, si le problème d'arrêt était calculable, nous pourrions automatiquement vérifier si un logiciel va se terminer / s'accrocher. une certaine entrée ou non. Nous n'aurions probablement plus de BSOD. Comme cela n'est pas possible, nous devons utiliser d'autres techniques pour garantir la qualité des logiciels (tels que les tests) et personne n'investit temps et argent pour développer un programme général de «vérification de terminaison». Je pense donc que ce résultat théorique a une énorme pertinence pratique.
Giorgio
4

D'autres ont commenté cela, mais je vais essayer d'écrire une réponse donnant mon point de vue.

J'aime bien la réponse de Robert Harvey et les commentaires de sa réponse, et j'aimerais les développer.

Je pense que vous devez présenter ces problèmes indécidables (comme la terminaison) de manière banale: par exemple, un outil IDE qui "vérifie si cette fonction renvoie toujours une valeur".

Lors de l'enseignement, mon exemple préféré était le refactoring ( équivalence de fonction, autre problème indécidable ). J'ai demandé:

comment vérifiez-vous si une fonction / programme fait de même après votre refactoring sympa? Bien sûr, nous avons des tests unitaires pour cela, mais ils ne couvrent pas tous les cas. Et ils sont ennuyeux à écrire ... Mais nous sommes programmeurs! Nous devons écrire un programme qui vérifie si ces deux fonctions produisent toujours le même résultat! Pourquoi n'essayez-vous pas de l'écrire?

ou, comme une variante peut-être plus proche de votre cas:

Nous avons ce code hérité écrit dans un ancien dialecte COBOL obscur, pour lequel aucune spécification et / ou compilateur n'existe. Nous n'avons que le programme. Toute notre entreprise en dépend, nous devons donc être sûrs à 100% que le nouveau code Java fait exactement la même chose dans chaque situation. La direction veut un programme qui le fasse, vérifiant tous les cas possibles, et estime que cela peut être fait en 6 à 8 semaines. Pourquoi n'essayez-vous pas de l'écrire?

Il ne s'agit pas d'écrire un tel programme. Ou une assez bonne approximation des exigences. Le but est de réaliser que cela ne peut PAS être fait de manière directe, ne gaspillez PAS d'innombrables nôtres en essayant de comprendre comment le faire (seulement pour réaliser que ce n'est pas possible), mais reconnaissez-le. "Ah! C'est indécidable! Ce n'est pas possible de le faire directement. J'ai besoin de trouver une manière différente, plus intelligente de le faire, avec une approximation suffisamment bonne".

Vous devez trouver un moyen de présenter le problème d'une manière reconnaissable et apparemment simple. Vous ne croiriez pas combien d'étudiants CS essaieront d'écrire un tel programme tout de suite ... avant de suivre un cours de calculabilité :)

Lorenzo Dematté
la source
Votre deuxième devis tente d'invoquer le problème d'arrêt de manière incorrecte; cependant, si nous savons que le programme COBOL fonctionne et peut l'exécuter dans un environnement de test (vm-clone tout PROD si nécessaire), le problème d'arrêt est exclu et nous pouvons essayer. Probablement à la main plutôt que par programme mais nous pouvons tout de même le faire. Nous pourrions couper en arbre toutes les formes d'entrée possibles si besoin est. Parce que le programme cible s'arrête, il en sera de même pour l'arborescence.
Joshua
2

En supposant que nous pouvons mettre de côté pour le moment les questions morales:

L'entreprise A a passé un contrat avec vous pour un moyen de communiquer entre les bureaux satellites A1 et A2 sans que personne d'autre que les personnes autorisées en A1 et A2 ne puisse comprendre la communication.

L'entreprise B vous a confié un moyen d'écouter intelligemment toutes les communications entre A1 et A2.

De toute évidence, vous ne pouvez pas faire les deux.

En raison de la façon dont les mathématiques fonctionnent (les mathématiques exactes font l'objet de recherches continues depuis 100 ans), l'une des exigences suivantes ne peut pas être satisfaite:

(1): Fournissez un algorithme de chiffrement qui ne peut pas être brisé par un attaquant avec une somme d'argent arbitraire disponible.

(2): Fournissez un algorithme de rupture de chiffrement pour un algorithme de chiffrement arbitraire qui s'exécute dans un délai raisonnable.

Joshua
la source
1
(3): Ne pas obtenir un autre emploi après que le marché a découvert que vous avez même tenté les deux
TruthOf42
1

J'ai récemment suivi un cours sur le modèle de processus métier et la notation ( BPMN ). Là, il est facile de voir que les flux de travail avec beaucoup trop de divisions, de jointures et de boucles deviennent rapidement impraticables (mais pas nécessairement impossibles , AFAIK) à comprendre et à contrôler (lorsque vous utilisez trop de divisions OR au lieu de divisions XOR).

Pour l'industrie du logiciel, je pense qu'il en va de même pour des problèmes similaires de "couverture de conditions multiples" dans l' analyse de couverture de code .

Pour une entreprise, la voie à suivre consiste à réduire l'espace du problème et à ne pas consacrer davantage de ressources au problème complexe. Dans mon exemple, ajoutez des contraintes au flux de travail (ou, dans l'analyse de la couverture de code, simplifiez le code), au lieu de travailler dur pour trouver tous, disons, N traces et résultats possibles où N est un nombre incroyablement élevé.

En dehors de cela, je pense qu'il y a de nombreux problèmes dans l' analyse de réseau / graphique qui sont impossibles à résoudre (essayer de déterminer une topologie de réseau en parcourant de manière itérative tous les chemins, etc.).

knb
la source
0

L'exemple classique essaie d' analyser le HTML avec des expressions régulières . Cela peut fonctionner avec des ensembles limités de HTML mais une solution générale est impossible, car ils ont des grammaires Chomsky différentes (comme le lien le montre clairement (ish)).

Plus généralement, certaines personnes n'aiment pas penser philosophiquement (comme votre collègue) et je ne suis pas sûr que vous puissiez discuter de votre façon de sortir d'un état d'esprit. Son premier point est certainement faux, mais son second pourrait simplement être une façon de dire que je n'ai pas besoin de m'inquiéter à ce sujet pour coder les formulaires Web pour la réception des marchandises. J'ai de la sympathie pour cela, mais parfois, connaître la théorie signifie que vous ne vous engagez pas à trouver le Saint Graal pendant le temps de travail.

Alistair Mackenzie
la source
-6

La réponse est peut-être que votre collègue a raison. Peut-être avez-vous mal compris Turing ou comment cela s'applique-t-il ici?

Toutes les machines sont finies, il n'y a donc pas de «vraies» machines de Turing et aucun programme qui ne s'arrêtera jamais. Un programme trivial qui exécute une boucle infinie simple pourrait durer 5 minutes ou 50 ans, mais sur une machine finie, il s'arrêtera. Un problème non trivial sans interruption tel que «calculer exactement pi» s'arrêtera également, car finalement le calcul dépassera la capacité de stocker d'autres chiffres.

Le résultat de Turing ne garantit rien de particulièrement utile sur les machines finies, donc votre quête est finalement infructueuse. Mieux vaut se concentrer sur combien de temps et combien d'argent et laisser l'infini aux mathématiciens.

Vous pouvez penser qu'un programme comme { while true: print "running"; print "halted"; }est un contre-exemple, mais ce n'est pas le cas. Ce programme a des effets secondaires qui peuvent ou non provoquer son arrêt. En ignorant les effets secondaires, il est possible de concevoir une preuve formelle que ce programme ne s'arrêtera pas. Dans cette question, nous ne nous intéressons qu'aux programmes qui échappent à la preuve formelle de non-arrêt, où la question de l'arrêt est indécidable. Ce n'est pas un tel programme.

Il peut être utile de distinguer Turing «fort» de Turing «faible». Les machines de Turing fortes sont en fait infinies et si elles ne s'arrêtent pas, elles fonctionneront pendant une durée infinie. Nous ne pouvons pas les construire.

Les machines de Turing faibles ont des limites finies de temps et d'espace, et ce sont les seules que nous pouvons construire. Nous sommes intéressés par des programmes dont il est impossible de prouver qu'ils s'arrêtent dans ces limites. Turing nous dit qu'il existe de tels programmes mais nous ne pouvons pas les identifier. Si les limites sont suffisamment basses, nous pouvons les identifier en écrivant le programme et en l'exécutant à ses limites.

L'essence de Turing est qu'il n'y a pas de raccourcis. La seule façon d'être certain qu'un problème est réalisable par calcul est d'écrire le programme, de l'exécuter et de le découvrir. Avec suffisamment de temps et d'argent, vous pouvez écrire tous les programmes, les exécuter indéfiniment et dans le temps, et trouver ceux qui produisent des résultats (les licols). Les autres seront toujours en cours d'exécution. Votre collègue a-t-il suffisamment de temps et d'argent pour le faire?

Sérieusement, le différend porte sur les limites. Turing et NP complete nous indiquent que certaines classes de problèmes ne peuvent pas être résolues par des ordinateurs dans un budget donné ou selon un calendrier donné, quelle que soit la taille de ce budget ou la générosité de ce calendrier. Les exemples de ce type de problème abondent: rupture des clés cryptographiques; optimiser les itinéraires pour effectuer des livraisons à des centaines d'adresses; boîtes d'emballage dans des camions; trouver des bugs dans les grands programmes!

Demandez donc à votre collègue un budget et un calendrier et promettez que vous pouvez produire un problème qui ne peut pas être résolu dans ce budget ou ce calendrier. Cette promesse sera très facile à tenir.

david.pfx
la source
2
L'essence du problème de l'arrêt est qu'il existe des classes de problèmes qui ne peuvent jamais être calculés, même avec du temps et de l'argent infinis. C'est ce que mon collègue refuse d'accepter.
Jesan Fafon
Ensuite, nous ne sommes pas d'accord. J'ai édité ma réponse, mais essentiellement le message est le même. Votre question telle qu'elle est posée n'a pas de réponse (ou pas celle que vous aimerez), mais sous-jacente, c'est un vrai problème et un vrai point à souligner. Si vous voulez gagner cet argument, vous allez devoir changer quelque peu de terrain et j'ai essayé de vous aider. [Rappelez-moi de ne pas essayer de répondre à des questions comme celle-ci à nouveau - les votes négatifs ne sont pas les bienvenus.]
david.pfx
2
@simon: Au risque de me répéter, il n'y a pas de programmes qui prennent un temps infini à terminer car il n'y a pas d'ordinateurs complets Turing, juste des approximations finies. Vous ne pouvez pas prouver qu'un programme arbitraire se terminera dans un laps de temps particulier par une méthode plus rapide que l'exécution réelle du programme. En pratique, toute phrase contenant le mot «infini» risque de ne pas avoir de sens.
david.pfx
3
while True: print "doing stuff"; print "Finished"; C'est un exemple de programme qui prend un temps infini pour se terminer. Il existe une quantité infinie d'autres programmes qui prennent également un temps infini à terminer. Nous créons régulièrement des programmes qui prennent un temps infini à compléter exprès. Ils sont appelés «processus de longue durée». La plupart des sites Web dynamiques en sont un exemple.
Singletoned
2
Le fait est sûrement qu'il existe des ensembles de programmes informatiques qui sont effectivement infinis, ils ne s'arrêteront jamais sous leur propre vapeur (nous appuierons sur break, coupons le courant, etc.), si nous les programmions dans une machine de Turing, ce serait courir sans s'arrêter. L'essence du problème de l'arrêt est qu'il n'y a aucun moyen, pratiquement ou théoriquement, de déterminer algorithmiquement les programmes qui ne s'arrêtent pas.
Alistair Mackenzie