Pourquoi les programmes ne peuvent-ils pas être prouvés?

Les épreuves sont des programmes.

La vérification formelle des programmes est un vaste domaine de recherche. (Voir, par exemple, le groupe de Carnegie Mellon .)

De nombreux programmes complexes ont été vérifiés; Par exemple, voir ce kernel écrit en Haskell .

Les programmes peuvent absolument se révéler corrects. Les programmes moche sont difficiles à prouver. Pour le faire même raisonnablement bien, vous devez faire évoluer le programme et prouver main dans la main.

Vous ne pouvez pas automatiser la preuve en raison du problème d’arrêt. Vous pouvez toutefois prouver manuellement les post-conditions et conditions préalables de toute instruction arbitraire ou séquence d’instructions.

Vous devez lire A Discipline of Programming de Dijsktra.

Ensuite, vous devez lire La science de la programmation de Gries.

Ensuite, vous saurez comment prouver que les programmes sont corrects.

Juste un petit commentaire à ceux qui ont évoqué l’inachèvement – ce n’est pas le cas pour tous les systèmes axiomatiques, seulement suffisamment puissants .

En d’autres termes, Godel a prouvé qu’un système axiomatique suffisamment puissant pour se décrire serait nécessairement incomplet. Cela ne signifie pas pour autant qu’il serait inutile, et comme d’autres l’ont fait, plusieurs tentatives de preuves de programmes ont été faites.

Le double problème (écrire des programmes pour vérifier les preuves) est également très intéressant.

Le problème d’arrêt ne fait que montrer qu’il existe des programmes qui ne peuvent pas être vérifiés. Une question beaucoup plus intéressante et pratique est de savoir quelle classe de programmes peut être officiellement vérifiée. Peut-être que tous les programmes qui intéressent pourraient (en théorie) être vérifiés. En pratique, jusqu’ici, seuls de très petits programmes ont été prouvés corrects.

Vous pouvez en fait écrire des programmes corrects. Microsoft, par exemple, a créé une extension du langage C # appelée Spec # qui inclut un démonstrateur de théorème automatisé. Pour java, il y a ESC / java . Je suis sûr qu’il y a beaucoup d’autres exemples.

( edit : apparemment, spec # n’est plus en cours de développement, mais les outils de contrat feront désormais partie de .NET 4.0 )

Je vois des affiches montrant à la main le problème de l’ arrêt ou les théorèmes d’incomplétude qui empêchent la vérification automatique des programmes. Ceci n’est bien sûr pas vrai; ces problèmes nous disent simplement qu’il est possible d’écrire des programmes qui ne peuvent être prouvés exacts ou incorrects . Cela ne nous empêche pas de construire des programmes qui sont manifestement corrects.

Si le sujet vous intéresse vraiment, laissez-moi d’abord vous recommander “The Science of Programming” de David Gries, un ouvrage d’introduction classique sur le sujet.

Il est effectivement possible de prouver que les programmes sont corrects dans une certaine mesure. Vous pouvez écrire des conditions préalables et des postconditions, puis prouver que, dans un état satisfaisant aux conditions préalables, l’état résultant après exécution répondra aux conditions préalables.

Là où ça devient difficile, cependant, ce sont les boucles. Pour ceux-ci, vous devez en outre trouver un invariant de boucle et pour afficher une terminaison correcte, vous devez trouver une fonction de limite supérieure sur le nombre maximum possible d’itérations restant après chaque boucle. Vous devez également être en mesure de montrer que cela diminue d’au moins un après chaque itération de la boucle.

Une fois que vous avez tout cela pour un programme, la preuve est mécanique. Mais malheureusement, il n’y a aucun moyen de dériver automatiquement les fonctions invariantes et liées pour les boucles. L’intuition humaine suffit pour les cas sortingviaux avec de petites boucles, mais de manière réaliste, les programmes complexes deviennent rapidement intraitables.

D’abord, pourquoi dites-vous que “les programmes NE PEUVENT PAS être prouvés”?

Que voulez-vous dire par “programmes” de toute façon?

Si par programmes vous voulez dire des algorithmes, ne connaissez-vous pas ceux de Kruskal? Dijkstra? MST? Prim’s Recherche binary? Tri par fusion? DP? Toutes ces choses ont des modèles mathématiques qui décrivent leurs comportements.

DÉCRIRE. Les mathématiques n’expliquent pas pourquoi les choses dessinent simplement une image du comment. Je ne peux pas vous prouver que le soleil se lèvera demain à l’est, mais je peux montrer les données là où il a fait ce truc.

Vous avez dit: “Si vous écrivez un programme informatique, comment se fait-il que vous puissiez prendre des œuvres éprouvées et les utiliser pour montrer la vérité de votre programme?

Attendez? Vous ne pouvez pas http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis

Je ne peux pas vous montrer la “vérité”, je programme autant que je ne peux pas vous montrer la “vérité” sur le langage. Les deux sont des représentations de notre compréhension empirique du monde. Pas sur “la vérité”. Mis à part le charabia, je peux vous démontrer mathématiquement qu’un algorithme de fusion sortingera les éléments d’une liste avec des performances O (nlogn), qu’un Dijkstra trouvera le chemin le plus court sur un graphe pondéré ou que l’algorithme d’Euclid vous trouvera le plus grand. diviseur commun entre deux nombres. La “vérité dans mon programme” dans ce dernier cas est peut-être que je vais vous trouver le plus grand commun diviseur entre deux nombres, vous ne pensez pas?

Avec une équation de récurrence, je peux vous décrire comment fonctionne votre programme Fibonacci.

Maintenant, la programmation informatique est-elle un art? Je pense bien que c’est le cas. Autant que les mathématiques.

Je ne viens pas d’un fond mathématique, alors pardonnez mon ignorance, mais que signifie “prouver un programme”? Qu’est-ce que tu prouves? La justesse? La justesse est une spécification que le programme doit vérifier pour être “correcte”. Mais cette spécification est décidée par un humain et comment vérifier que cette spécification est correcte?

À mon avis, il y a des bogues dans le programme parce que les humains ont du mal à exprimer ce qu’ils veulent vraiment. alt text http://www.processdevelopers.com/images/PM_Build_Swing.gif

Alors qu’est-ce que tu prouves? Bugs causés par un manque d’attention?

De plus, quels sont les axiomes de la programmation? Les vérités très atomiques du domaine?

J’ai suivi un cours intitulé Programmation basée sur le contrat (page d’accueil du cours: http://www.daimi.au.dk/KBP2/ ). Voici ce que je peux extrapoler du cours (et d’autres cours que j’ai suivis)

Vous devez formellement (mathématiquement) définir la sémantique de votre langue. Pensons à un langage de programmation simple; celui qui ne contient que des variables globales, ints, int arrays, arithmétique, if-then-else, while, assignation et do-nothing [vous pouvez probablement utiliser un sous-ensemble de n’importe quel langage grand public comme “implémentation”].

Un état d’exécution serait une liste de paires (nom de la variable, valeur de la variable). Lire “{Q1} S1 {Q2}” comme “l’instruction d’exécution S1 vous emmène de l’état d’exécution Q1 à l’état Q2”.

Un axiome serait alors "if both {Q1} S1 {Q2} and {Q2} S2 {Q3}, then {Q1} S1; S2 {Q3}" . C’est-à-dire que si l’instruction S1 vous mène de l’état Q1 à Q2 et que l’instruction S2 vous emmène de Q2 à Q3, alors “S1; S2” (S1 suivi de S2) vous emmène de l’état Q1 à l’état Q3.

Un autre axiome serait "if {Q1 && e != 0} S1 {Q2} and {Q1 && e == 0} S2 {Q2}, then {Q1} if e then S1 else S2 {Q2}" .

Maintenant, un peu de raffinement: les Qn dans {} seraient en réalité des déclarations sur les états, pas sur les états eux-mêmes.

Supposons que M (out, A1, A2) soit une instruction qui fusionne deux tableaux sortingés et stocke le résultat dans out, et que tous les mots que j’utilise dans l’exemple suivant ont été exprimés formellement (mathématiquement). Puis "{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}"

On peut essayer de le prouver en utilisant les axiomes ci-dessus (quelques autres seraient probablement nécessaires. Vous aurez probablement besoin d’une boucle, pour une).

J’espère que cela illustre un peu ce à quoi pourraient bien ressembler les programmes de démonstration. Et croyez-moi, il faut beaucoup de travail, même pour des algorithmes apparemment simples, pour les prouver. Je sais, j’ai lu beaucoup de tentatives 😉

[Si vous lisez ceci: votre transfert a été bon, ce sont tous les autres qui m’ont causé des maux de tête ;-)]

Bien sûr, ils peuvent, comme d’autres l’ont posté.

Prouver un très petit sous-programme correct est un bon exercice que IMHO chaque premier cycle d’un programme d’études lié à la programmation devrait être tenu de faire. Cela vous donne un bon aperçu de la manière de rendre votre code clair, facilement révisable et maintenable.

Cependant, dans la réalité, son utilisation pratique est limitée.

Tout d’abord, tout comme les programmes ont des bogues, il en va de même pour les preuves mathématiques. Comment prouver qu’une preuve mathématique est vraiment correcte et ne comporte aucune erreur? Vous ne pouvez pas Et, par exemple, des erreurs mathématiques ont été découvertes, parfois des années plus tard.

Deuxièmement, vous ne pouvez pas prouver qu’un programme est correct sans avoir à priori une définition sans ambiguïté de ce que le programme est censé faire. Mais toute définition non ambiguë de ce qu’un programme est censé faire est un programme. (Bien que cela puisse être un programme dans une sorte de langage de spécification pour lequel vous n’avez pas de compilateur.) Par conséquent, avant de pouvoir prouver qu’un programme est correct, vous devez d’abord avoir un autre programme équivalent et connu à l’avance. être correct. Donc, tout cela est inutile.

Je recommanderais de suivre l’article classique ” No Silver Bullet ” de Brooks.

Il y a beaucoup de recherches dans ce domaine. Comme d’autres l’ont déjà dit, les concepts dans un langage de programme sont complexes, et cela ne fait qu’empirer lorsque l’on essaie de valider ou de prouver pour des entrées données.

Cependant, de nombreuses langues autorisent les spécifications, les entrées acceptables (conditions préalables) et permettent également de spécifier le résultat final (post-conditions).

Ces langues comprennent: B, événement B, Ada, Fortran.

Et bien sûr, il existe de nombreux outils conçus pour nous aider à prouver certaines propriétés des programmes. Par exemple, pour prouver la liberté de l’impasse, il est possible de réaliser son programme via SPIN.

Il existe également de nombreux outils qui nous aident également à détecter les erreurs logiques. Cela peut se faire par parsing statique (goanna, satabs) ou exécution réelle du code (gnu valgrind?).

Cependant, il n’y a pas un seul outil qui permette vraiment de prouver un programme entier, depuis la création (spécification), la mise en œuvre et le déploiement. La méthode B est proche, mais la vérification de son implémentation est très faible. (Cela suppose que les humains sont infaillibles dans la traduction de speicficaiton en implémentation).

En guise de note, lorsque vous utilisez la méthode B, vous vous retrouverez souvent à créer des preuves complexes à partir d’axiomes plus petits. (Et la même chose s’applique aux autres démonstrateurs de théorèmes exhasustifs).

Ils peuvent. J’ai passé de nombreuses heures comme étudiant de première année à faire des épreuves de correction de programme.

La raison pour laquelle ce n’est pas pratique à une échelle macro est que l’écriture d’une preuve de programme a tendance à être beaucoup plus difficile que l’écriture du programme. De plus, les programmeurs ont tendance à créer des systèmes et non à écrire des fonctions ou des programmes.

À petite échelle, je le fais parfois mentalement pour des fonctions individuelles, et j’ai tendance à organiser mon code pour le rendre facile à vérifier.

Il y a un article célèbre sur le logiciel de la navette spatiale. Ils font des preuves, ou quelque chose d’équivalent. C’est incroyablement coûteux et long. Ce niveau de vérification peut être nécessaire pour eux, mais pour les fabricants de logiciels grand public ou commerciaux, avec les techniques actuelles, votre concurrent mange votre repas avec une solution à 99,9% à 1% du coût. Personne ne va payer 5000 $ pour un MS Office légèrement plus stable.

Si vous recherchez la confiance, l’alternative à la démonstration des programmes est de les tester. Ceci est plus facile à comprendre et peut être automatisé. Cela permet également la classe de programmes pour laquelle les preuves ne sont mathématiquement pas possibles, comme décrit ci-dessus.

Surtout, aucune preuve ne remplace les tests d’acceptation: *

• Ce n’est pas parce qu’un programme fait vraiment ce qu’il dit qu’il ne fait pas ce que l’utilisateur veut qu’il fasse.

  • Sauf si vous pouvez prouver que ce qu’il dit, c’est ce que l’utilisateur dit vouloir.

    • Ce que vous devez ensuite prouver, c’est ce qu’ils veulent vraiment , car, en tant qu’utilisateur, ils ne savent presque certainement pas ce qu’ils veulent. etc. Reductio ad absurdum.

* sans parler de l’unité, de la couverture, de la fonctionnalité, de l’intégration et de tous les autres types de tests.

J’espère que cela vous aidera sur votre chemin.

Quelque chose qui n’a pas été mentionné ici est la méthode B, qui est un système basé sur une méthode formelle. Il a été utilisé pour développer le système de sécurité du métro parisien. Il existe des outils pour soutenir le développement de B et de l’événement B, notamment Rodin .

Non seulement vous pouvez prouver des programmes, vous pouvez laisser votre ordinateur construire des programmes à partir de preuves. Voir Coq . Vous n’avez donc même pas à vous soucier de la possibilité d’avoir commis une erreur dans votre implémentation.

Les théorèmes de Godel nonobstant … Quel serait le point? Quelles “vérités” simplistes voudriez-vous prouver? Que voudriez-vous tirer de ces vérités? Bien que je puisse manger ces mots … où est la praticité?

Les programmes peuvent être prouvés. Il est facile de les écrire dans un langage comme par exemple le ML Standard du New Jersey (SML / NJ).

Votre déclaration est large et attrape beaucoup de poissons.

La ligne de fond est la suivante: certains programmes peuvent certainement être prouvés corrects. Tous les programmes ne peuvent pas être prouvés corrects.

Voici un exemple sortingvial qui, vous le savez, est exactement le même type de preuve qui a détruit la théorie des ensembles à l’époque: créez un programme capable de déterminer si lui-même est correct et, s’il le trouve, donnez une réponse incorrecte.

C’est le théorème de Gödel, simple et clair.

Mais ce n’est pas si problématique, car nous pouvons prouver de nombreux programmes.

Supposons un langage purement fonctionnel (c’est-à-dire Haskell). Les effets secondaires peuvent être pris en compte assez clairement dans ces langues.

Prouver qu’un programme produit le bon résultat nécessite que vous spécifiiez:

1. une correspondance entre les types de données et les ensembles mathématiques
2. une correspondance entre les fonctions de Haskell et les fonctions mathématiques
3. un ensemble d’axiomes spécifiant les fonctions que vous êtes autorisé à construire à partir des autres, et la construction correspondante du côté mathématique.

Cet ensemble de spécifications est appelé sémantique dénotationnelle . Ils vous permettent de prouver la raison des programmes utilisant les mathématiques.

La bonne nouvelle est que la “structure des programmes” (point 3 ci-dessus) et la “structure des ensembles mathématiques” sont assez similaires (le mot à la mode est topos ou catégorie fermée cartésienne ), donc 1 / les preuves du côté mathématique sera facilement transféré dans des constructions programmatiques 2 / les programmes que vous écrivez sont facilement mathématiquement corrects.

Lisez le problème en suspens (qui concerne la difficulté de prouver quelque chose d’aussi simple qu’un programme se termine ou non). Fondamentalement, le problème est lié au théorème d’incomplétude de Gödel.

Certaines parties des programmes peuvent être prouvées. Par exemple, le compilateur C # qui vérifie statiquement et garantit la sécurité du type, si la compilation réussit. Mais je soupçonne que l’essentiel de votre question est de prouver qu’un programme fonctionne correctement. Beaucoup d’algorithmes (je n’ose pas dire le plus) peuvent être prouvés corrects, mais un programme entier ne peut probablement pas être prouvé de manière statique à cause de ce qui suit:

• La vérification nécessite que toutes les twigs possibles (appels, ifs et interupts) soient traversées, ce qui, dans le code de programme avancé, présente une complexité de temps super cubique (par conséquent, il ne se terminera jamais dans un délai raisonnable).
• Certaines techniques de programmation, que ce soit en créant des composants ou en utilisant la reflection, empêchent de prévoir statiquement l’exécution du code (vous ne savez pas comment un autre programmeur utilisera votre bibliothèque et le compilateur a du mal à invoquer la fonctionnalité.

Et ce ne sont que quelques …

Si le programme a un objective bien défini et des hypothèses initiales (en ignorant Godel …), cela peut être prouvé. Trouvez tous les nombres premiers, x, pour 6 <= x <= 10, votre réponse est 7 et cela peut être prouvé. J'ai écrit un programme qui joue NIM (le premier programme Python que j'ai écrit) et, en théorie, l'ordinateur gagne toujours après que le jeu tombe dans un état où l'ordinateur peut gagner. Je n'ai pas pu le prouver comme étant vrai, mais il est vrai (mathématiquement par une preuve de somme binaire numérique), à ​​moins que je commette une erreur dans le code. Ai-je fait une erreur, non sérieusement, est-ce que quelqu'un peut me dire si ce programme est battable?

Certains théorèmes mathématiques ont été “prouvés” avec un code informatique tel que le théorème des quatre couleurs . Mais il y a des objections, car comme vous l’avez dit, pouvez-vous prouver le programme?

De plus, quels sont les axiomes de la programmation? Les vérités très atomiques du domaine?

Les opcodes sont-ils les “vérités atomiques”? Par exemple en voyant …

 mov ax,1 

… un programmeur ne pourrait-il pas affirmer comme étant axiomatique que, sauf problème matériel, après avoir exécuté cette instruction, le registre ax la CPU contiendrait désormais 1 ?

Si vous écrivez un programme informatique, comment se fait-il que vous puissiez prendre des œuvres éprouvées et les utiliser pour montrer la vérité de votre programme?

Le “travail précédent” pourrait alors être l’environnement d’exécution dans lequel le nouveau programme s’exécute.

Le nouveau programme peut être prouvé: en plus des preuves formelles, il peut être prouvé “par inspection” et par diverses formes de “tests” (y compris “tests d’acceptation”).

Comment prouves-tu un Picasso?

Si les logiciels s’apparentent plus au design indussortingel ou à l’ingénierie qu’à l’art, une meilleure question pourrait être “Comment prouver un pont ou un avion?”

prouver qu’un programme est correct ne peut être fait que par rapport à la spécification du programme; c’est possible mais coûteux / long

Certains systèmes CASE produisent des programmes plus faciles à tester que d’autres – mais là encore, cela repose sur une sémantique formelle de la spécification …

… et donc comment prouver la spécification correcte? Droite! Avec plus de spécifications!

J’ai lu un peu à ce sujet, mais il y a deux problèmes.

Tout d’abord, vous ne pouvez pas prouver une chose abstraite appelée la correction. Vous pouvez, si les choses sont correctement configurées, prouver que deux systèmes formels sont équivalents. Vous pouvez prouver qu’un programme implémente un ensemble de spécifications, et il est plus facile de le faire en construisant la preuve et le programme plus ou moins en parallèle. Par conséquent, les spécifications doivent être suffisamment détaillées pour fournir des éléments de preuve, et la spécification est donc un programme . Le problème de l’écriture d’un programme pour satisfaire un objective devient le problème de l’écriture d’une spécification détaillée formelle d’un programme pour satisfaire un objective, et ce n’est pas nécessairement un pas en avant.

Deuxièmement, les programmes sont compliqués. Donc, sont des preuves de l’exactitude. Si vous pouvez faire une erreur en écrivant un programme, vous pouvez en faire une preuve. Dijkstra et Gries m’ont dit essentiellement que si j’étais un parfait mathématicien, je pouvais être un bon programmeur. La valeur ici est que la démonstration et la programmation sont deux processus de reflection quelque peu différents, et au moins dans mon expérience, je fais différentes sortes d’erreurs.

D’après mon expérience, les programmes de démonstration ne sont pas inutiles. Lorsque j’essaie de faire quelque chose que je peux décrire formellement, prouver que l’implémentation est correcte élimine un grand nombre d’erreurs difficiles à trouver, en laissant principalement les erreurs idiotes, que je peux facilement détecter lors des tests. Sur un projet qui doit produire un code extrêmement exempt de bogues, cela peut être un complément utile. Il n’est pas adapté à toutes les applications et ce n’est certainement pas une solution miracle.

Comme d’autres l’ont souligné, certains programmes peuvent être prouvés.

Un problème en pratique est cependant que vous avez besoin de quelque chose (c’est-à-dire une hypothèse ou un théorème) que vous voulez prouver. Donc, pour prouver quelque chose à propos d’un programme, vous devez d’abord une description formelle de ce qu’il doit faire (par exemple, avant et après les conditions).

En d’autres termes, vous avez besoin d’une spécification formelle du programme. Mais obtenir une spécification raisonnable (et encore moins rigoureuse) est déjà l’une des choses les plus difficiles du développement logiciel. Par conséquent, il est généralement très difficile de prouver des choses intéressantes sur un programme (réel).

Il y a cependant des choses qui peuvent être (et ont été) plus facilement formalisées (et éprouvées). Si vous pouvez au moins prouver que votre programme ne tombera pas en panne, c’est déjà quelque chose :-).

BTW, certains avertissements / erreurs du compilateur sont essentiellement (simples) des preuves sur un programme. Par exemple, le compilateur Java prouvera que vous n’accédez jamais à une variable non initialisée dans votre code (sinon, cela vous donnera une erreur de compilation).

Je n’ai pas lu toutes les réponses, mais à mon avis, prouver des programmes est inutile, c’est pourquoi personne ne le fait.

Si vous avez un projet relativement petit / moyen (disons 10K lignes de code), alors la preuve sera probablement 10k lignes, sinon plus.

Pensez-y, si le programme peut avoir des bogues, la preuve peut aussi avoir des “bugs”. Peut-être aurez-vous besoin d’une preuve pour la preuve!

Une autre chose à considérer, les programmes sont très très formels et précis. Vous ne pouvez pas obtenir plus rigoureux et formel, car le code du programme doit être exécuté par une machine très stupide.

Alors que les épreuves vont être lues par les humains, elles ont tendance à être moins rigoureuses que le code actuel.

Les seules choses que vous voudrez prouver sont les algorithmes de bas niveau qui fonctionnent sur des structures de données spécifiques (par exemple, quicksort, insertion dans un arbre binary, etc.).

Ces choses sont quelque peu compliquées, on ne voit pas immédiatement pourquoi elles fonctionnent et / ou si elles fonctionneront toujours. Ce sont également des éléments de base pour tous les autres logiciels.

La plupart des réponses sont axées sur la pratique et ce n’est pas grave: dans la pratique, vous ne vous souciez pas de l’épreuvage formel. Mais qu’est-ce qui est en théorie?

Les programmes peuvent être prouvés comme un énoncé mathématique. Mais pas dans le sens que tu voulais dire! Dans tout cadre suffisamment puissant, il existe des énoncés mathématiques (et des programmes) qui ne peuvent être prouvés! Voir ici

Tant de bruit ici, mais je vais de toute façon crier au vent …

“Prouvez correctement” a différentes significations dans différents contextes. Dans les systèmes formels , “prouver que c’est correct” signifie qu’une formule peut être dérivée d’autres formules éprouvées (ou axiomatiques). “Prouvez correctement” dans la programmation montre simplement que le code est équivalent à une spécification formelle. Mais comment prouver la spécification formelle correcte? Malheureusement, il n’y a aucun moyen de montrer une spécification comme étant exempte de bogues ou une solution présentant un problème réel autre que le test.

Juste mes 2 centimes, en ajoutant aux choses intéressantes déjà là.

De tous les programmes qui ne peuvent pas être prouvés, les plus courants sont ceux qui effectuent des E / S (une interaction imprévisible avec le monde ou les utilisateurs). Même les épreuves automatisées oublient parfois que les “programmes” éprouvés s’exécutent sur du matériel physique, pas l’idéal décrit par le modèle.

D’un autre côté, les preuves mathématiques ne se soucient guère du monde. Une question récurrente avec les mathématiques est si elle décrit quelque chose de réel. Il est soulevé chaque fois que quelque chose de nouveau comme des nombres imaginaires ou des espaces non-euclidiens est inventé. La question est alors oubliée car ces nouvelles théories sont de si bons outils. Comme un bon programme, ça marche.