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

https://stackoverflow.com/questions/476959

20-08-2019
|

Question

Pourquoi un programme informatique ne peut-il pas être prouvé comme un énoncé mathématique? Une preuve mathématique est construite sur d’autres preuves, qui sont construites à partir de preuves supplémentaires et jusqu’à des axiomes - ces vérités que nous considérons comme évidentes.

Les programmes informatiques ne semblent pas avoir une telle structure. Si vous écrivez un programme informatique, comment pouvez-vous utiliser des œuvres déjà éprouvées et les utiliser pour montrer la vérité de votre programme? Vous ne pouvez pas puisque aucun n'existe. De plus, quels sont les axiomes de la programmation? Les vérités atomiques du terrain?

Je n'ai pas de bonnes réponses à ce qui précède. Mais il semble que le logiciel ne puisse pas être prouvé car il s’agit d’art et non de science. Comment prouver un Picasso?

La solution

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. Voir, par exemple, ce noyau écrit en Haskell .

Autres conseils

Les programmes peuvent absolument être vérifiés. Les programmes moche sont difficiles à prouver. Pour le faire, même raisonnablement bien, vous devez faire évoluer le programme et vérifier les preuves main dans la main.

Vous ne pouvez pas automatiser la preuve à cause du problème qui s’arrêtait. Cependant, vous pouvez prouver manuellement les conditions préalables et les conditions préalables de toute instruction ou séquence d'instructions arbitraires.

Vous devez lire la une discipline de programmation de Dijsktra.

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

Vous saurez alors comment prouver que les programmes sont corrects.

Juste un petit commentaire à ceux qui ont évoqué l'incomplétude - ce n'est pas le cas pour tous les systèmes axiomatiques, mais seulement ceux qui sont suffisamment puissants .

En d’autres termes, Godel a prouvé qu’un système axiomatique assez puissant pour se décrire serait nécessairement incomplet. Cela ne signifie pas pour autant que cela serait inutile et que, comme d'autres l'ont indiqué, diverses tentatives de vérification de programme ont été effectuées.

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

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

( modifier : apparemment, la spécification n'est plus développée, mais les outils de contrat feront partie de .NET 4.0 )

Je vois des affiches qui agitent la main à propos du problème bloquant ou théorèmes d'incomplétude qui empêchent supposément la vérification automatique des programmes. Ceci n'est bien sûr pas vrai; ces problèmes nous indiquent simplement qu'il est possible d'écrire des programmes dont il est impossible de prouver qu'ils sont corrects ou incorrects . Cela ne nous empêche pas de construire des programmes qui sont parfaitement corrects.

Le problème d'arrêt indique uniquement qu'il existe des programmes qui ne peuvent pas être vérifiés. Une question beaucoup plus intéressante et plus pratique est de savoir quelle classe de programmes peut être vérifiée formellement. Peut-être que tous les programmes qui intéressent pourraient (en théorie) être vérifiés. ~~En pratique, jusqu'à présent, seuls de très petits programmes ont été validés.~~

Si le sujet vous intéresse vraiment, permettez-moi d'abord de vous recommander la "&" Science de la programmation & "de David Gries, une introduction classique sur le sujet.

Il est en fait possible de prouver que les programmes sont corrects dans une certaine mesure. Vous pouvez écrire des conditions préalables et des conditions postérieures, puis prouver que si l'état obtenu répond à ces conditions, l'état résultant de l'exécution respectera les conditions postérieures.

Mais ce qui devient difficile, ce sont les boucles. Pour ceux-ci, vous devez en outre rechercher un invariant de boucle et pour afficher la terminaison correcte, vous devez rechercher une fonction de limite supérieure du nombre maximal d'itérations restantes après chaque boucle. Vous devez également pouvoir montrer que cela diminue d'au moins une 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’ya aucun moyen de dériver automatiquement les fonctions invariantes et liées pour les boucles. L’intuition humaine suffit pour les cas triviaux avec de petites boucles, mais en réalité, les programmes complexes deviennent rapidement intraitables.

Tout d’abord, pourquoi dites-vous & "Les programmes NE PEUVENT PAS être prouvés &";

Qu'entendez-vous par " programmes " de toute façon?

Si par programmes vous entendez des algorithmes, ne connaissez-vous pas ceux de Kruskal? Dijkstra? MST? Prim's? Recherche binaire? 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 le pourquoi des choses, elles dessinent simplement le comment. Je ne peux pas vous prouver que le soleil se lèvera demain à l'est, mais je peux montrer aux données où il a agi de la sorte.

Vous avez dit: " Si vous écrivez un programme informatique, comment pouvez-vous utiliser des travaux déjà éprouvés et les utiliser pour montrer la vérité de votre programme? Vous ne pouvez pas puisque rien n'existe & ";

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

Je ne peux pas vous montrer & «vérité &»; Je suis un programme autant que je ne peux pas vous montrer & «Vérité &»; sur la langue. Les deux sont des représentations de notre compréhension empirique du monde. Pas sur & "La vérité &". Mettant de côté tout le charabia, je peux vous démontrer mathématiquement qu’un algorithme mergesort va trier les éléments d’une liste avec des performances de O (nlogn), qu’un Dijkstra trouvera le chemin le plus court sur un graphe pondéré, ou que l’algorithme d’Euclide vous trouvera le meilleur diviseur commun entre deux nombres. La & Quot; vérité dans mon programme & Quot; dans ce dernier cas, je vous trouverai peut-être le plus grand commun diviseur entre deux nombres, vous ne pensez pas?

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

Maintenant, la programmation informatique est-elle un art? Je pense que oui. Autant que les mathématiques.

Je ne viens pas d'un contexte mathématique, alors pardonnez mon ignorance, mais que & "prouve un programme &"; signifier? Que prouves-tu? La justesse? L'exactitude est une spécification que le programme doit vérifier pour être & "Correct" & ";. Mais cette spécification est décidée par un humain, et comment vérifiez-vous que cette spécification est correcte?

À mon avis, il y a des bogues dans le programme parce que les humains ont des difficultés à exprimer ce qu'ils veulent vraiment. texte alt http://www.processdevelopers.com/images/PM_Build_Swing.gif

Alors, que prouves-tu? Bugs causés par le manque d'attention?

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

J'ai suivi un cours intitulé Programmation à contrat (page d'accueil du cours: http: // www.daimi.au.dk/KBP2/ ). Voici ce que je peux extrapoler à partir du cours (et des autres cours que j'ai suivis)

Vous devez définir formellement (mathématiquement) la sémantique de votre langue. Pensons à un langage de programmation simple; une qui ne contient que des variables globales, ints, int tableaux, arithmétiques, if-then-else, tandis que assignation et do-nothing [vous pouvez probablement utiliser un sous-ensemble de n'importe quel langage courant comme & "mise en oeuvre &" ; de ceci].

Un état d'exécution serait une liste de paires (nom de variable, valeur de variable). Lire & Quot; {Q1} S1 {Q2} & Quot; comme & "; l'instruction d'exécution S1 vous fait passer 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 fait passer de l'état Q1 à Q2 et si l'instruction S2 vous fait passer de Q2 à Q3, alors & Quot; S1; S2 & Quot; (S1 suivi de S2) vous fait passer 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 fait des déclarations concernant des états, pas des états eux-mêmes.

Supposons que M (out, A1, A2) est une instruction qui fusionne deux tableaux trié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). Alors "{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}" est l'affirmation selon laquelle M applique correctement l'algorithme de fusion.

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, par exemple).

J'espère que cela illustre un peu ce à quoi pourraient ressembler des programmes corrects. Et croyez-moi, il faut beaucoup de travail, même pour des algorithmes apparemment simples, pour prouver leur exactitude. Je sais, j'ai lu beaucoup de tentatives ;-)

[si vous lisez ceci: votre main était très bien, ce sont toutes les autres qui m'ont causé des maux de tête; -)]

Bien sûr, ils peuvent le faire, comme d'autres l'ont fait savoir.

Prouver qu'un très petit sous-programme est correct est un bon exercice que tous les étudiants de premier cycle d'un programme menant à un programme lié à la programmation doivent être obligatoires . Cela vous donne une bonne idée de la façon de rendre votre code clair, facilement révisable et maintenable.

Cependant, dans le monde réel, son utilisation pratique est limitée.

Tout d’abord, tout comme les programmes ont des bogues, les preuves mathématiques aussi. Comment prouver qu'une preuve mathématique est vraiment correcte et ne comporte aucune erreur? Tu ne peux pas. Et à titre d’exemple contraire, des erreurs ont été découvertes dans nombre d’épreuves mathématiques publiées, parfois des années plus tard.

Deuxièmement, vous ne pouvez pas prouver qu'un programme est correct sans avoir «a priori» une définition sans ambiguïté de ce qu'il est censé faire. Mais toute définition sans ambiguïté de ce qu’un programme est censé faire est un programme. (Bien qu'il puisse s'agir d'un programme dans un 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 disposer d'un autre programme équivalent, connu à l'avance. être correct. Ainsi, le CQFD est inutile.

Je recommanderais de rechercher le classique & "; Pas de solution miracle &"; article de Brooks.

Il existe de nombreuses recherches dans ce domaine. comme d’autres l’ont déjà dit, les constructions dans un langage de programme sont complexes et cela ne fait que s’aggraver lorsque vous essayez de valider ou de prouver des entrées.

Cependant, de nombreuses langues permettent des spécifications, sur quelles entrées sont acceptables (conditions préalables), et permettent également de spécifier le résultat final (conditions de post).

Ces langages incluent: B, Event B, Ada, fortran.

Et, bien entendu, de nombreux outils sont conçus pour nous aider à prouver certaines propriétés des programmes. Par exemple, pour prouver la liberté de blocage, vous pouvez exécuter leur programme via SPIN.

De nombreux outils nous aident également à détecter les erreurs de logique. Cela peut être fait via une analyse statique (goanna, satabs) ou une exécution réelle du code (gnu valgrind?).

Cependant, il n’existe pas d’outil permettant de prouver un programme complet, depuis le début (spécification), la mise en oeuvre et le déploiement. La méthode B est proche, mais sa vérification de la mise en œuvre est très très faible. (Cela suppose que les humains sont infaillibles dans la traduction de la spéicficaiton en implantation).

En guise de remarque, lorsque vous utilisez la méthode B, vous vous retrouvez souvent en train de construire des preuves complexes à partir d'axiomes plus petits. (Et il en va de même pour les autres prouveurs de théorèmes exhasustive).

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

La raison pour laquelle ce n’est pas pratique à une macro-échelle est que rédiger une preuve d’un programme a tendance à être beaucoup plus difficile que d’écrire un programme. De plus, les programmeurs actuels ont tendance à construire 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 qu'il soit facile à vérifier.

Il y a un article célèbre sur le logiciel de navette spatiale. Ils font des preuves, ou quelque chose d'équivalent. C'est incroyablement coûteux et prend du temps. Ce niveau de vérification peut être nécessaire pour eux, mais pour tout type de société de logiciels grand public ou commercial, avec les techniques actuelles, votre déjeuner sera consommé par un concurrent qui fournira une solution à 99,9% pour 1% du coût. Personne ne paiera 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 sont mathématiquement impossibles, comme décrit ci-dessus.

Surtout, aucune preuve ne peut remplacer les tests d'acceptation: *

Le fait qu'un programme fasse vraiment ce qu'il dit ne signifie pas qu'il fait ce que l'utilisateur veut qu'il fasse.
- À moins que ne puissiez prouver que ce qu'il dit être fait est ce que l'utilisateur dit qu'il veut.
  - 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 oublier l'unité, la couverture, le fonctionnement, l'intégration et 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 formel basé sur la méthode. Il a été utilisé pour développer le système de sécurité du métro parisien. Il existe des outils disponibles pour prendre en charge le développement B et Event B, notamment Rodin .

Vous pouvez non seulement prouver des programmes, mais également leur permettre de construire des programmes à partir de preuves. Voir Coq . Ainsi, vous n’aurez même pas à vous inquiéter de la possibilité d’une erreur dans votre mise en œuvre.

Les théorèmes de Godel nonobstant ... Quel serait le but ? Quelles & Quot; vérités & Quot; simplistes! voudriez-vous prouver? Que voudriez-vous tirer de ces vérités? Bien que je puisse manger ces mots ... où est le côté pratique?

Les programmes PEUVENT être prouvés. C’est très facile si vous les écrivez dans un langage tel que, par exemple, la norme ML du New Jersey (SML / NJ).

Votre déclaration est large, vous allez donc prendre beaucoup de poissons.

En résumé, il est certain que certains programmes peuvent s'avérer corrects. Tous les programmes ne peuvent pas être vérifiés.

Voici un exemple trivial qui, remarquez-vous, est exactement le même type de preuve que celle qui a détruit la théorie des ensembles: créez un programme capable de déterminer si elle est correcte et si elle trouve qu'elle est / em> correct, donne une réponse incorrecte.

C'est le théorème de G! & # 246; del, clair et simple.

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

Supposons un langage purement fonctionnel (ie Haskell). Les effets secondaires peuvent être pris en compte assez proprement dans ces langues.

Pour prouver qu'un programme produit le bon résultat, vous devez spécifier:

une correspondance entre les types de données et les ensembles mathématiques

une correspondance entre les fonctions de Haskell et les fonctions mathématiques

un ensemble d'axiomes spécifiant les fonctions que vous êtes autorisé à construire à partir des autres et la contruction 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 que vous faites du côté mathématique seront facilement transférées dans des constructions programmatiques 2 / les il est facile de montrer que les programmes que vous écrivez sont mathématiquement corrects.

Renseignez-vous sur le problème de blocage (qui concerne la difficulté de prouver quelque chose d'aussi simple comme si un programme se termine ou non). Fondamentalement, le problème est lié au théorème d'inachèvement de G & # 246; 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. On peut prouver que de nombreux algorithmes (je n'ose pas dire le plus souvent) sont corrects, mais un programme complet ne peut probablement pas être prouvé de manière statique en raison de ce qui suit:

La vérification nécessite le franchissement de toutes les branches possibles (appels, ifs et interruptions), ce qui, dans le code de programme avancé, présente une complexité temporelle super-cubique (et ne se terminera donc jamais dans un délai raisonnable).

Certaines techniques de programmation, qu'il s'agisse de créer des composants ou d'utiliser une réflexion, empêchent de prédire de manière statique l'exécution du code (vous ne savez pas comment un autre programmeur utilisera votre bibliothèque et le compilateur a du mal à prévoir comment la réflexion se déroulera. un consommateur invoquera la fonctionnalité.

Et ceux-ci ne sont que quelques-uns ...

Si le programme a un objectif bien défini et des hypothèses de départ (en ignorant Godel ...), cela peut être prouvé. Trouvez tous les nombres premiers, x, pour 6 & Lt; = x & Lt; = 10, votre réponse est 7 et cela peut être prouvé. J'ai écrit un programme qui exécute NIM (le premier programme Python J'ai jamais écrit) et en théorie, l'ordinateur gagne toujours lorsque le jeu tombe dans un état dans lequel l'ordinateur peut gagner. Je n'ai pas été capable de prouver que c'est vrai, mais c'est vrai (mathématiquement par une preuve de somme binaire numérique), sauf si je fais une erreur dans le code. Ai-je commis une erreur, non sérieusement, quelqu'un peut-il 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 atomiques du terrain?

Les opcodes sont-ils les & "vérités atomiques &"; Par exemple en voyant ...

mov ax,1

... un programmeur ne pourrait-il pas affirmer de manière évidente que, sauf dans le cas d'un problème matériel, le registre ax de la CPU, après avoir exécuté cette instruction, contiendrait maintenant 1?


Si vous écrivez un programme informatique, comment pouvez-vous utiliser des travaux déjà éprouvés et les utiliser pour montrer la vérité de votre programme?

Le ". travail précédent " il pourrait alors s'agir de l'environnement d'exécution dans lequel le nouveau programme est exécuté.

Le nouveau programme peut être prouvé: hormis les preuves formelles, il peut être prouvé " par inspection " et par diverses formes de " tester " (y compris " test d’acceptation ").


Comment prouver un Picasso?

Si un logiciel ressemble davantage à un design ou à une ingénierie industriels qu’à un 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 / prend du temps

Certains systèmes CASE produisent des programmes plus aptes aux preuves que d'autres - mais là encore, cela repose sur une sémantique formelle de la spécification ...

... et comment prouver que les spécifications sont correctes? 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 quelque chose d’abstrait appelé correction. Vous pouvez, si tout est configuré correctement, prouver que deux systèmes formels sont équivalents. Vous pouvez prouver qu'un programme implémente un ensemble de spécifications. 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 une preuve, par conséquent, elles constituent en réalité un programme . Le problème de l'écriture d'un programme pour atteindre un objectif devient le problème de l'écriture d'une spécification détaillée formelle d'un programme pour atteindre un objectif, et ce n'est pas nécessairement un progrès.

Deuxièmement, les programmes sont compliqués. Il en va de même pour les preuves d'exactitude. Si vous pouvez faire une erreur en écrivant un programme, vous pouvez en faire une preuve. Dijkstra et Gries m'ont dit, pour l'essentiel, que si j'étais un mathématicien parfait, je pourrais être un bon programmeur. La valeur ici est que prouver et programmer sont deux processus de pensée quelque peu différents, et au moins d'après mon expérience, je commets différentes sortes d'erreurs.

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

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

Cependant, un problème pratique réside dans le fait que vous avez d’abord besoin de quelque chose (c’est-à-dire une hypothèse ou un théorème) que vous voulez prouver. Donc, pour prouver quelque chose au sujet d’un programme, vous devez d’abord une description formelle de ce qu’il devrait faire (par exemple, avant et après conditions).

En d'autres termes, vous avez besoin d'une spécification formelle du programme. Mais obtenir une spécification raisonnable (et encore moins formelle 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).

Cependant, certaines choses peuvent être (et ont été) plus facilement formalisées (et prouvées). Si vous pouvez au moins prouver que votre programme ne plantera pas, c'est déjà quelque chose: -).

BTW, certains avertissements / erreurs du compilateur sont essentiellement des preuves (simples) d’un programme. Par exemple, le compilateur Java prouvera que vous n’avez jamais accès à une variable non initialisée dans votre code (sinon, vous obtiendrez une erreur du compilateur).

Je n'ai pas lu toutes les réponses, mais ce que je vois, prouver les programmes est inutile, c'est pourquoi personne ne le fait.

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

Pensez-y, si le programme peut avoir des bogues, la preuve peut aussi avoir & "; bogues &"; Peut-être aurez-vous besoin d'une preuve pour la preuve!

Autre chose à considérer, les programmes sont 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 donc tendance à être moins rigoureuses que le code réel.

Les seuls éléments que vous voudrez prouver seront des algorithmes de bas niveau qui fonctionnent sur des structures de données spécifiques (par exemple, un tri rapide, une insertion dans un arbre binaire, etc.).

Ces choses sont un peu compliquées, il n’est pas immédiatement évident de savoir pourquoi elles fonctionnent et / ou si elles fonctionneront toujours. Ils constituent également des éléments de base pour tous les autres logiciels.

La plupart des réponses se sont concentrées sur la pratique et c'est correct: dans la pratique, vous ne vous souciez pas de la correction formelle. Mais quelle est la théorie?

Les programmes peuvent être prouvés comme un énoncé mathématique. Mais pas dans le sens où vous vouliez 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 quand même crier au vent ...

" Prouver correct " a différentes significations dans différents contextes. Dans les systèmes formels , & Quot; prouver que c'est correct & Quot; signifie qu'une formule peut être dérivée d'autres formules éprouvées (ou axiomatiques). " Prouver correct " en programmation montre simplement que le code est équivalent à une spécification formelle. Mais comment prouver que les spécifications formelles sont correctes? Malheureusement, il n’existe aucun moyen de démontrer qu’une spécification est exempte de bogues ou d’apporter une solution à un problème réel, si ce n’est par le biais de tests.

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 exécutent des opérations d’IO (certaines interactions imprévisibles avec le monde ou les utilisateurs). Même les preuves automatisées oublient parfois que & "Prouvé &"; programmes " fonctionne sur du matériel physique, pas sur le matériel idéal décrit par le modèle.

De l’autre côté, les preuves mathématiques ne s’intéressent guère au monde. Une question récurrente avec Maths 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 un espace non-euclidien, est inventé. Ensuite, la question est oubliée car ces nouvelles théories sont de si bons outils. Comme un bon programme, cela fonctionne.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow