Pourquoi ne peut-être des programmes éprouvés?
Pourquoi pas un programme d'ordinateur être prouvé comme un rapport mathématique peut? Une preuve mathématique est construit sur d'autres preuves, qui sont construits à partir encore plus de preuves et jusqu'aux axiomes, des vérités vérités que nous détenons comme allant de soi.
Les programmes d'ordinateur ne semblent pas disposer d'une telle structure. Si vous écrivez un programme d'ordinateur, comment est-ce que vous pouvez prendre précédente prouvé œuvres et de les utiliser pour montrer la vérité de votre programme? Vous ne pouvez pas car il n'en existe aucun. En outre, ce sont les axiomes de la programmation? La très atomique vérités du champ?
Je n'ai pas de bonnes réponses à la ci-dessus. Mais il semble que le logiciel ne peut pas être prouvé, car c'est de l'art et non de la science. Comment voulez-vous prouver un Picasso?
- Gödel a prouvé(!) que dans tout système formel d'axiomes, il existe des énoncés pour lesquels il n'est pas possible de prouver leur valeur true ou false. Vous faites l'hypothèse que toutes les mathématiques déclarations peuvent être prouvée, ce qui n'est malheureusement pas le cas.
- Blé: Où est @4thspace en supposant que toutes les mathématiques états peut être prouvé?
- Merci pour la sortir Mitch.
- Espérons que cette question n'est pas fermé,
- La question est plutôt de pesimistic, et son a pas vrai hypothèse de toute façon
- Cette question est du charabia. Comment voulez-vous prouver une grenouille? Comment faites-vous raser un éternuement? Veuillez fermer.
Vous devez vous connecter pour publier un commentaire.
Preuves sont programmes.
Vérification formelle des programmes est un énorme domaine de recherche. (Voir, par exemple, le groupe de l'université Carnegie Mellon.)
De nombreux programmes complexes ont été vérifiés; voir, par exemple, ce noyau écrit en Haskell.
Programmes absolument peut être avérée correcte. Moche programmes sont difficiles à prouver. Pour le faire, même raisonnablement bien, vous avez à faire évoluer le programme et la preuve de main en main.
Vous ne pouvez pas automatiser la preuve en raison du problème de l'arrêt. Vous pouvez, cependant, manuellement prouver les post-conditions et les conditions préalables de tout arbitraire de la déclaration, ou d'une séquence d'instructions.
Vous devez lire Dijsktra de Une Discipline de Programmation.
Ensuite, vous devez lire Gries' La Science de la Programmation.
Alors vous saurez comment prouver des programmes corrects.
Juste un petit commentaire pour ceux qui ont fait jusqu'incomplétude, ce n'est pas le cas pour tous systèmes axiomatiques, seulement suffisamment puissant ceux.
En d'autres termes, Gödel a prouvé qu'un système axiomatique assez puissant pour décrire lui-même serait nécessairement incomplète. Cela ne veut pas dire qu'il serait inutile toutefois, et comme d'autres l'ont lié à plusieurs tentatives de programme de preuves ont été apportées.
Le problème dual (l'écriture de programmes pour vérifier les preuves) est également très intéressante.
Le problème de l'arrêt montre seulement qu'il y a des programmes qui ne peuvent être vérifiées. Beaucoup plus intéressant et plus pratique question est ce que la classe de programmes peut être formellement vérifié. Peut-être, pour chaque programme, quiconque se soucie peut (en théorie) être vérifiée.
Dans la pratique, jusqu'à présent, seuls les très petits programmes ont été prouvé correct.Vous pouvez en fait écrire prouvable de programmes corrects. Microsoft, par exemple, a créé une extension du langage C# appelé Spec# qui comprend un prouveur automatique. Pour java, il est ESC/java. Je suis sûr qu'il ya beaucoup plus d'exemples.
(modifier: apparemment spec# n'est plus développé, mais le contrat d'outils va devenir une partie de .NET 4.0)
Je vois des affiches à la main en agitant sur le problème de l'arrêt ou les théorèmes d'incomplétude qui sont censées empêcher la vérification automatique de programmes. Bien sûr ce n'est pas vrai; ces questions simplement dire que c'est possible d'écrire des programmes qui ne peut pas être prouvée pour être correcte ou incorrecte. Cela ne nous empêche pas de construire des programmes qui sont prouvable correcte.
Si vous êtes vraiment intéressés par le sujet, permettez-moi d'abord vous recommandons de David Gries' "La Science de la Programmation", un classique de l'introduction du travail sur le sujet.
Il est réellement possible de prouver des programmes de corriger, dans une certaine mesure. Vous pouvez écrire des préconditions et les postconditions et ensuite prouver que, étant donné un état qui satisfait aux conditions préalables, l'état résultant, après l'exécution de satisfaire les postconditions.
Où il est difficile, cependant, est les boucles. Pour ces derniers, vous avez également besoin de trouver un invariant de boucle et de montrer la terminaison correcte vous avez besoin de trouver une borne supérieure de la fonction sur le nombre maximal d'itérations restantes après chaque tour de boucle. Vous devez également être en mesure de démontrer que cela diminue d'au moins l'un après chaque itération de la boucle.
Une fois que vous avez tout cela pour un programme, la preuve, c'est mécanique. Mais malheureusement, il n'y a aucun moyen de dériver automatiquement l'invariant et les fonctions liées aux boucles. L'intuition d'une personne suffit pour les cas triviaux avec de petites boucles, mais de façon réaliste, des programmes complexes rapidement devenus insolubles.
Tout d'abord, pourquoi êtes-vous en disant: "les programmes ne POUVEZ PAS être prouvé"?
Qu'entendez-vous par "programmes" de toute façon?
Si par les programmes que vous avez le sens des algorithmes ne savez-vous pas Kruskal est? Dijkstra est? MST? Prim est? Binaire De Recherche? Mergesort? DP? Toutes ces choses ont des modèles mathématiques qui décrivent leurs comportements.
DÉCRIRE. Les mathématiques ne pas expliquer le pourquoi des choses, il dessine simplement une image de la façon dont. Je ne peux pas vous prouver que le Soleil se lèvera demain sur l'Est, mais je peux montrer les données là où il a fait cette chose sur le passé.
Vous dit:
"Si vous écrivez un programme d'ordinateur, comment est-ce que vous pouvez prendre précédente prouvé œuvres et de les utiliser pour montrer la vérité de votre programme? Vous ne pouvez pas car il n'en existe pas"
Attendre? Vous ne POUVEZ PAS?
http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis
Je ne peux pas vous montrer la "vérité" j'ai un programme que je ne peux pas vous montrer la "vérité" sur la langue. Les deux sont des représentations de notre connaissance empirique du monde. Pas sur "la vérité". Mettre tout le charabia de côté, je peux montrer mathématiquement que mergesort algorith permettra de trier les éléments d'une liste avec O(nlogn) de la performance, qu'un Dijkstra va trouver le plus court chemin sur un graphe pondéré, ou que d'Euclide l'algorithme va vous trouver le plus grand commun diviseur entre deux nombres. La "vérité dans mon programme" dans ce dernier cas, peut-être que je vais vous trouver le plus grand commun diviseur entre deux numéros, vous ne pensez pas?
Avec une récurrence équation que je peut délimiter à vous comment votre Fibonacci programme fonctionne.
Maintenant, est programmation informatique un art? Je pense qu'il est. Autant que les mathématiques.
Je ne viens pas d'un contexte mathématique, donc pardonnez mon ignorance, mais qu'est "pour prouver un programme" signifie?
De quoi êtes-vous prouver? L'exactitude? L'exactitude est une spécification que le programme doit vérifier pour être "la bonne". Mais cette spécification est décidé par un humain, et comment vérifiez-vous que cette spécification est correcte?
À mon avis, il y a des bugs dans le programme parce que les humains ont de la difficulté à exprimer ce qu'ils veulent vraiment.
le texte d'alt http://www.processdevelopers.com/images/PM_Build_Swing.gif
Donc quoi êtes-vous le prouver? Bugs causés par un manque d'attention?
requiresetensuresdans la programmation en c.J'ai TA ed un cours appelé " Contrat de Base de la Programmation (cours page d'accueil: http://www.daimi.au.dk/KBP2/). Voici ce que je peux extrapoler à partir de la cours (et d'autres cours que j'ai pris)
Vous avez officiellement (mathématiquement) définir la sémantique de votre langue. Pensons à un langage de programmation simple; un qui a des variables globales seulement, ints, int tableaux, l'arithmétique, de l'if-then-else, while, d'affectation et de ne rien faire [vous pouvez probablement utiliser un sous-ensemble de toute langue dominante comme une "mise en œuvre" de ce].
Un état de l'exécution serait une liste de couples (nom de la variable, la valeur de la variable). Lire "{T1} S1 {T2}" comme "l'instruction en cours d'exécution S1 vous emmènera de l'exécution de l'état Q1 à l'état Q2".
Un axiome serait alors
"if both {Q1} S1 {Q2} and {Q2} S2 {Q3}, then {Q1} S1; S2 {Q3}". C'est, si l'instruction S1-vous de l'état de T1 à T2, et de la déclaration S2 vous prend de T2 à T3, puis "S1; S2 (S1 suivie par S2) vous emmène de l'état Q1 à l'état T3.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: le Qn dans {}'s seraient en fait des déclarations sur les états, et non les états eux-mêmes.
Supposons que M(out, A1, A2) est une déclaration qui fait une fusion de deux tableaux triés et stocke le résultat dans, et que tous les mots que j'utilise dans l'exemple suivant ont été exprimées formellement (mathématiquement). Puis
"{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}"est la revendication tha M correctement implémente l'algorithme de fusion.On peut essayer de le prouver en utilisant les axiomes ci-dessus (quelques autres seraient probablement nécessaires. Vous êtes susceptible d'avoir besoin d'une boucle, par exemple).
J'espère que cela illustre un peu de ce que la preuve de programmes corrects pourrait ressembler. Et croyez-moi: il faut un beaucoup de travail, même apparemment simple, les algorithmes, afin de prouver qu'ils ont raison. Je sais, j'ai lu beaucoup de tentatives 😉
[si vous lisez ceci: votre à la main en était bien, c'est tous les autres qui m'ont causé des maux de tête ;-)]
Bien sûr, ils peuvent, comme d'autres l'ont publié.
Révèle d'une très petite sous-routine correcte est un bon exercice qui à mon humble avis tous les étudiants de premier cycle dans une programmation liées au programme de baccalauréat doit être nécessaire à faire. Il vous donne une grande perspicacité dans la réflexion sur la façon de faire de votre code clair, facilement vérifiable et maintenable.
Cependant, dans le monde réel, il est d'une utilité limitée.
D'abord, tout comme les programmes ont des bugs, donc, faire de preuves mathématiques. Comment prouver qu'une preuve mathématique est vraiment correct et ne pas avoir des erreurs? Vous ne pouvez pas. Et pour le contre-exemple, n'importe quel nombre de publié des preuves mathématiques ont eu des erreurs découvertes, parfois des années plus tard.
Deuxième, vous ne pouvez pas prouver qu'un programme est correct sans avoir a priori une définition sans ambiguïté de ce que le programme est censé faire. Mais toute définition sans ambiguïté de ce que le programme est censé faire, c'est un programme. (Bien qu'il peut être un programme dans une sorte de langage de spécification que vous n'avez pas de compilateur.) Par conséquent, avant de vous peut prouver qu'un programme est correct, vous devez d'abord avoir un autre programme qui est l'équivalent, et est connu à l'avance pour être correct. Donc, CQFD, le tout est futile.
Je recommanderais au suivi de la classique "Pas la panacée" article par Brooks.
Theres beaucoup de recherche dans ce domaine.. comme d'autres l'ont dit, les constructions à l'intérieur d'un programme de langue sont complexes, et cela ne fait que s'aggraver, lorsque vous essayez de valider ou de prouver, pour tous les intrants.
Cependant, beaucoup de langues permettent de cahier des charges, sur ce que les entrées sont acceptables (conditions préalables), et permettent également de spécifier le résultat final (post-conditions).
Ces langues sont: B, Cas B, Ada, fortran.
Et bien sûr, il existe de nombreux outils qui sont conçus pour nous aider à prouver certaines propriétés sur les programmes. Par exemple, pour prouver blocage de la liberté , on pourrait crunch leur programme par le biais de SPIN.
Il ya aussi beaucoup des outils là-bas aussi nous aider à détecter les erreurs de logique. Cela peut être fait par le biais de l'analyse statique (goanna, satabs) ou l'exécution de code (gnu valgrind?).
Cependant, il n'est pas un outil qui permet de prouver un programme complet, de la conception (cahier des charges), la mise en œuvre et de déploiement. La méthode B est proche, mais sa mise en œuvre, le contrôle est très très faible. (Il suppose que les humains sont infalible dans la traduction de speicficaiton dans la mise en oeuvre).
Comme une note de côté, lors de l'utilisation de la méthode B, vous aurez souvent trouver vous-même la construction complexe des épreuves à partir de petits axiomes. (Et la même chose s'applique pour les autres exhasustive démonstrateurs).
Ils le peuvent. J'ai passé de nombreuses heures en tant que freshman collège de faire le programme de l'exactitude des preuves.
La raison pour laquelle il n'est pas pratique sur une échelle macro, c'est que l'écriture d'une preuve d'un programme tend à être beaucoup plus difficile que d'écrire le programme. Aussi, les programmeurs ont tendance aujourd'hui à construire des systèmes, de ne pas écrire des fonctions ou des programmes.
Sur une micro-échelle, il m'arrive de le faire mentalement pour des fonctions individuelles, et ont tendance à organiser mon code pour les rendre faciles à vérifier.
Il y a un célèbre article sur la navette spatiale logiciel. Ils ne épreuves, ou quelque chose d'équivalent. Il est incroyablement coûteux et prend du temps. Ce niveau de vérification peut être nécessaire pour eux, mais pour tout type de consommateur ou d'un logiciel commercial de l'entreprise, avec les techniques actuelles, vous aurez votre déjeuner mangé par un concurrent qui offre à 99,9% de solution à 1% du coût. Personne ne va payer 5000 $pour un MS Office c'est un peu plus stable.
Si vous êtes à la recherche pour la confiance, l'alternative à la preuve de programmes est à l'épreuve. C'est plus facile à comprendre et peut être automatisé. Il permet également la classe de programmes pour lesquels les preuves sont mathématiquement pas possible, comme décrit ci-dessus.
Au-dessus de tous, aucune preuve n'est un substitut pour le passage des tests d'acceptation:*
Juste parce qu'un programme ne vraiment faire ce qu'il dit il le fait, ne signifie pas qu'il fait ce que l'utilisateur veut faire.
Sauf vous pouvez prouver que ce qu'il dit il le fait est que ce que l'utilisateur dit qu'ils veulent.
*ne pas mentionner l'unité, de la couverture, fonctionnels, d'intégration et de tous les autres types de tests.
Espère que cela vous aide sur votre chemin.
Quelque chose qui n'a pas été mentionné ici est le B - Méthode qui est une méthode basée sur le système. Il a été utilisé pour développer le système de sécurité du métro de Paris.
Il existe des outils disponibles à l'appui de B et l'Événement B de développement, notamment Rodin.
Non seulement pouvez-vous prouver programmes, vous pouvez permettre à votre ordinateur de construire des programmes de preuves. Voir Coq. Donc, vous n'avez même pas à vous soucier de la possibilité de l'avoir fait une erreur dans votre mise en œuvre.
Théorèmes de Godel nonobstant...à Quoi servirait-il? Ce que simpliste "vérités" qu'aimeriez-vous prouver? Que voudriez-vous tirer de ces vérités? Alors que je peut manger ces mots...où est la pratique?
Programmes PEUT être prouvé. C'est calme facile si vous pouvez les écrire dans la langue, comme par exemple la Norme ML de New Jersey (SML/NJ).
Votre déclaration est large c'est donc d'attraper beaucoup de poissons.
La ligne de fond est: certains programmes peuvent certainement être prouvé correct. Tous les programmes peuvent pas être prouvé correct.
Voici un exemple trivial qui, vous l'esprit, c'est exactement le même genre de preuve qui a détruit la théorie des ensembles de retour dans la journée: faire un programme qui peut déterminer si lui-même est correcte, et s'il constate qu'il est corriger, donner une réponse incorrecte.
C'est le théorème de Gödel, pure et simple.
Mais ce n'est pas si problématique, puisque l'on peut prouver de nombreux programmes.
Supposons un point de vue purement fonctionnel de la langue (c'est à dire Haskell). Les effets secondaires peuvent être pris tout à fait correctement en compte dans ces langues.
Prouver que un programme produit le bon résultat nécessite de préciser:
Ce cahier des charges est appelé denotational sémantique. Ils vous permettent de prouver la raison sur les programmes utilisant les mathématiques.
La bonne nouvelle, c'est que la "structure de programmes" (point 3 ci-dessus) et la "structure mathématique des ensembles" sont assez similaires (le mot à la mode est topos, ou cartésienne fermée catégorie), donc 1/les preuves que vous faites sur les mathématiques côté pourrez facilement être transférés dans programmatique constructions 2/les programmes que vous écrivez sont facilement démontré mathématiquement correct.
Lire sur le problème de l'arrêt (qui est sur la difficulté de prouver quelque chose d'aussi simple que de savoir si un programme se termine ou pas). Fondamentalement, le problème est lié à Gödel du théorème d'incomplétude.
Certaines parties de programmes ne peut être prouvée. Par exemple, le compilateur C# de manière statique de vérifier et de garantir la sécurité de type, si la compilation réussit.
Mais je soupçonne que le cœur de votre question est de prouver qu'un programme s'exécute correctement. De nombreux (je n'ose pas dire la plupart) des algorithmes peut être s'est avéré être correct, mais tout un programme ne peut probablement pas être prouvé de manière statique, pour les raisons suivantes:
Et ce sont quelques-unes...
Si le programme a un objectif bien défini et les hypothèses de départ (en ignorant Godel...) il peut être prouvé. Trouver tous les nombres premiers,x, 6<=x<=10, votre réponse est 7 et qui peut être prouvé. J'ai écrit un programme qui joue NIM (le premier programme en Python que j'ai jamais écrit) et dans la théorie de l'ordinateur gagne toujours après le match tombe dans un état dans lequel l'ordinateur peut gagner. Je n'ai pas été en mesure de prouver qu'elle est vraie, mais il EST vrai (mathématiquement par un numérique de la somme binaire de la preuve) je crois que si je fait une erreur dans le code. J'ai fait une erreur, non, sérieusement, quelqu'un peut-il me dire si ce programme est battable?
Il y a quelques théorèmes mathématiques qui ont été "prouvé" par le code de l'ordinateur comme la théorème des quatre couleurs. Mais il y a des objections, car comme vous l'avez dit, pouvez-vous prouver le programme?
Sont les opcodes le "atomic vérités"? Par exemple, en le voyant ...
... pourraient ne pas un programmeur de s'affirmer en tant de soi que, en l'absence d'un problème matériel, après l'exécution de cette instruction, le PROCESSEUR est
axregistre contiennent maintenant1?La précédente "travail", alors peut-être que l'environnement d'exécution dans lequel le nouveau programme s'exécute.
Le nouveau programme peut être prouvé: en dehors de preuves formelles, il peut être prouvé "par" inspection " et les diverses formes de "testing" (y compris "le test d'acceptation").
Si le logiciel est plus comme dessin ou modèle industriel ou en génie de l'art, une meilleure question pourrait être "comment voulez-vous prouver un pont, ou un avion?"
prouver un programme correct ne peut être fait que par rapport à la spécification du programme; c'est possible, mais coûteux et chronophage
certains CAS, les systèmes de produire des programmes plus adaptés aux preuves que d'autres - mais encore une fois, cela repose sur une sémantique formelle de la spécification...
...et alors, comment pouvez-vous prouver que la spécification correcte? La droite! Avec plus de caractéristiques!
J'ai lu un peu sur ce sujet, mais il y a deux problèmes.
Tout d'abord, vous ne pouvez pas prouver quelque chose abstraite appelée exactitude. Vous pouvez, si les choses sont bien établies, de prouver que les deux systèmes sont équivalents. Vous pouvez prouver que un programme implémente un ensemble de spécifications, et il est plus facile de le faire par la construction de la preuve et de programmes plus ou moins en parallèle. Par conséquent, le cahier des charges doit être suffisamment détaillée pour fournir quelque chose à prouver contre, et donc la spécification est effectivement un programme. Le problème de l'écriture d'un programme pour satisfaire un but devient le problème de l'écrit formel de spécification détaillée d'un programme visant à satisfaire un but, et ce n'est pas nécessairement un pas en avant.
Deuxièmement, les programmes sont compliquées. Donc, sont des preuves de la justesse. Si vous pouvez faire une erreur d'écriture d'un programme, bien sûr que tu peux en faire un à prouver. Dijkstra et de Gries m'a dit, en substance, que si j'étais un parfait mathématicien que je pouvais être un bon programmeur. La valeur ici est que la preuve et la programmation sont deux quelque peu différents processus de la pensée, et au moins dans mon expérience, je fais différentes sortes d'erreurs.
Dans mon expérience, la preuve de programmes n'est pas inutile. Quand je suis en train de faire quelque chose que je peux décrire formellement, prouvant la mise en œuvre correcte élimine beaucoup de dur-à-trouver des erreurs, principalement en laissant le muet, qui je peut l'attraper facilement dans les tests. Sur un projet qui doit produire extrêmement code sans bug, il peut être un complément utile. Il n'est pas adapté pour chaque application, et ce n'est certainement pas la panacée.
Comme d'autres l'ont souligné, certains programmes peuvent en effet être prouvée.
Un problème dans la pratique, cependant, est que vous devez d'abord le quelque chose (c'est à dire une hypothèse ou théorie) que vous voulez prouver. Afin de prouver quelque chose à propos d'un programme que vous avez d'abord besoin d'une description formelle de ce qu'il devrait faire (ex: pré - et post-conditions).
En d'autres termes, vous avez besoin d'une spécification formelle du programme. Mais encore raisonnable (beaucoup moins rigoureux) spécification est déjà l'une des choses les plus difficiles dans le développement de logiciels. Par conséquent, il est généralement très difficile de prouver intéressant choses à propos d'un (du monde réel) du programme.
Il y a cependant certaines choses qui peuvent être (et ont été) plus facilement formalisé (et prouvé). Si vous pouvez au moins prouver que votre programme ne va pas planter, c'est déjà quelque chose :-).
BTW, certains avertissements du compilateur/les erreurs sont essentiellement (simple) des preuves au sujet d'un programme. E. g., le compilateur Java se prouver que vous n'avez jamais accéder à une variable non initialisée dans votre code (dans le cas contraire, il vous donnera une erreur du compilateur).
Je n'ai pas lu toutes les réponses, mais la façon dont je le vois, la preuve de programmes est inutile, c'est pourquoi personne ne le fait.
Si vous avez une relativement petite/moyenne de projet (par exemple, 10K lignes de code), alors la preuve est probablement va être aussi 10k lignes, si ce n'est plus.
Penser, si le programme peut avoir des bugs, la preuve peut également avoir des "bugs". Peut-être que vous aurez besoin d'une preuve de la preuve!
Une autre chose à considérer, les programmes sont très très formel et précis. Vous ne pouvez pas obtenir la plus rigoureuse et formelle, parce que le code du programme qui doit être exécuté par un très bête de la machine.
Alors que les preuves sont va être lu par des humains, de sorte qu'ils ont tendance à être moins rigoureux que le code réel.
Les seules choses que vous aurez envie de prouver sont de bas niveau des algorithmes qui fonctionnent sur des structures de données (par exemple, tri rapide, l'insertion d'un arbre binaire, etc).
Ces choses sont un peu compliquées, il n'est pas immédiatement évident pourquoi ils travaillent et/ou si elle le sera toujours. Ils sont aussi des blocs de construction de base pour tous les autres logiciels.
La plupart des réponses axées sur la pratique et c'est ok: dans la pratique, vous n'avez pas de soins officiels de vérification. Mais ce qui est en théorie?
Programmes peut être prouvé comme un rapport mathématique peut. Mais pas dans le sens que vous vouliez dire!
En tout suffisamment puissant cadre, il y a des instructions mathématiques (et programmes) qui ne peut pas être prouvée! Voir ici
Donc beaucoup de bruit ici, mais je vais le crier dans le vent de toute façon...
"Prouver correcte" a des significations différentes dans des contextes différents. Dans systèmes formels, "avérer" signifie qu'une formule peut être dérivée à partir d'autres prouvée (ou axiomes) les formules. "Avérer" dans la programmation de la montre, tout simplement, code pour avoir l'équivalent d'une spécification formelle. Mais comment voulez-vous prouver le formel spec-elle correcte? Malheureusement, il n'existe aucun moyen de montrer une spécification pour être exempt de bogues ou d'une solution de tout problème réel autrement que par le biais de tests.
Juste mes 2 cents, en y ajoutant les choses intéressantes déjà là.
De tous les programmes qui ne peut pas être prouvée, les plus courants sont ceux qui effectuent des IO (certains propriété plutôt imprévisible interaction avec le monde ou les utilisateurs). Même automatisé des épreuves parfois oublier que "prouvé" programmes" sur une partie du matériel physique, pas l'idéal décrit par le modèle.
De l'autre côté preuves mathématiques ne se soucient pas beaucoup de monde. Une question récurrente avec les Maths, c'est que si elle décrit quelque chose de réel. Il est relevé à chaque fois quelque chose de nouveau, comme les nombres imaginaires ou non-euclidien de l'espace est inventé. Alors la question est oublié que ces nouvelles théories sont tels de bons outils. Comme un bon programme, il fonctionne, tout simplement.
De moins abstraits point de fo de la vue, de prouver que quelque chose est une question de réduire le champ de l'incertitude éprouvée série null. C'est un vœu pieux, car la perfection ne peut pas être atteint dans le monde réel.
Un programme d'ordinateur peut être sensiblement correcte et l'échec dans le monde réel si son environnement ne sont pas (ou ne peuvent pas) être prouvé:
le noyau de système d'exploitation, les pilotes et le tout en mode utilisateur des bibliothèques et exécuté simultanément des programmes doit être prouvée, y compris leur directs et indirects à court terme et à long terme des effets secondaires,
le matériel doit toujours se comporter comme prévu (y compris avec le pouvoir, les pannes, l'eau des inondations, des tremblements de terre, EMF interférences, etc.),
les utilisateurs finaux doivent toujours se comporter comme prévu (le fameux facteur "X").
Automatique de correction d'erreur est mis en œuvre dans divers composants (RAM, disques, automates, etc.) mais néanmoins défaillances matérielles se produisent encore - la création d'une cascade d'erreurs et/ou des échecs dans...
provably correctprogrammes.Et je ne suis même pas essayer d'épilogue à propos de la fin de l'utilisateur de la créativité...
Ainsi, un programme (correctement) nominale
provably correctne signifie pas qu'il estprovably safedans la vie réelle.Cela signifie que, pour la série considérée dans un d'étude défini (qui ne peut être qu'un sous-ensemble du monde réel), ce programme va se comporter comme prévu.