Warum können keine Programme nachgewiesen werden?

StackOverflow https://stackoverflow.com/questions/476959

Frage

Warum kann Sie nicht ein computer-Programm bewiesen werden nur als eine mathematische Aussage kann?Ein mathematischer Beweis aufgebaut ist, die auf anderen Beweise, die aufgebaut sind aus noch mehr Beweise, und auf nach unten zu Axiome - Wahrheiten, Wahrheiten, die wir halten als selbstverständlich.

Computer-Programme scheinen nicht zu haben eine solche Struktur.Wenn Sie schreiben ein computer-Programm, wie ist es so, dass Sie können nehmen vorherigen nachweislich funktioniert, und verwenden Sie Sie, um zeigen die Wahrheit von deinem Programm?Sie können nicht, da keiner vorhanden ist.Weiter, was sind die Axiome der Programmierung?Die sehr atomic Wahrheiten des Feldes?

Ich habe keine guten Antworten auf die oben genannten.Aber es scheint, die software kann nicht bewiesen werden, weil es Kunst ist und keine Wissenschaft.Wie beweisen Sie ein Picasso?

War es hilfreich?

Lösung

sind Programme.

Formale Verifikation von Programmen ist ein großen Forschungsbereich. (Siehe zum Beispiel die Gruppe an der Carnegie Mellon .)

Viele komplexe Programme überprüft wurden; siehe zum Beispiel dieses Kernel geschrieben in Haskell .

Andere Tipps

Programme absolut können nachgewiesen werden, korrekt sein. Lousy Programme sind schwer zu beweisen. Um es zu tun, auch gut vernünftig, haben Sie das Programm und den Nachweis Hand in Hand zu entwickeln.

Sie können nicht Automate der Beweis wegen des Halteproblem. Sie können jedoch unter Beweis stellen manuell die post Bedingungen und Voraussetzungen von jeder beliebigen Aussage oder eine Folge von Anweisungen.

Sie müssen Dijsktra eine Disziplin der Programmierung .

Dann müssen Sie lesen Gries' The Science of Programming .

Dann werden Sie wissen, wie Programme richtig zu beweisen.

Nur ein kleiner Kommentar zu denen, die Unvollständigkeit gebracht - es ist nicht der Fall für alle axiomatischen Systeme, nur stark genug diejenigen

.

Mit anderen Worten, erwies sich als Gödel, dass ein axiomatisches System stark genug, um mich selbst zu beschreiben, notwendigerweise unvollständig wäre. Dies bedeutet nicht, es wäre jedoch nutzlos sein, und wie andere verknüpft haben, wurden verschiedene Versuche bei Programm Beweise gemacht worden.

Das duale Problem (die Programme schreiben, Beweise zu prüfen) ist auch sehr interessant.

Sie können in der Tat beweisbar korrekte Programme schreiben. Microsoft zum Beispiel hat eine Erweiterung der Sprache C # erstellt namens Spec # die beinhaltet eine automatisierte Theorem Prover. Für Java gibt es ESC / java . Ich bin sicher, es gibt viele weitere Beispiele gibt.

( Bearbeiten : scheinbar spec # wird nicht mehr weiterentwickelt, aber der Vertrag Tools werden Teil .NET 4.0 ) werden

Ich sehe einige Poster von Hand winken über die Halteproblem oder

Das Halteproblem zeigt nur, dass es Programme gibt, die nicht überprüft werden können. Eine viel interessanter und praktischere Frage ist, welche Klasse von Programmen kann wird formal verifiziert. Vielleicht könnte jedes Programm jemand kümmert sich um (in der Theorie) überprüft werden. In der Praxis bisher nur sehr kleine Programme wurden erweist sich als richtig.

Wenn Sie wirklich am Thema interessiert sind, lassen Sie mich zunächst David Gries' "The Science of Programming", eine klassische Einführungs Arbeit zum Thema empfehlen.

Es ist tatsächlich möglich, Programme zu einem gewissen Grad richtig zu beweisen. Sie können schreiben, Vorbedingungen und Nachbedingungen und dann beweisen, dass ein Zustand gegeben, dass die Voraussetzungen erfüllt, die sich ergebende Zustand nach Ausführung werden die Nachbedingungen erfüllen.

Wenn es schwierig wird, ist jedoch Schleifen. Für diese benötigen Sie zusätzlich noch eine Schleifeninvariante und zeigen korrekte Terminierung Sie eine Obergrenze Funktion auf die maximal mögliche Anzahl von Iterationen finden Nötige zu finden, nach jeder Schleife verbleiben. Sie müssen auch in der Lage sein zu zeigen, dass dies verringert sich um mindestens eine nach jeder Iteration durch die Schleife.

Wenn Sie für ein Programm, das alles haben, ist der Beweis, mechanisch. Aber leider gibt es keine Möglichkeit, automatisch die Invarianten und gebundene Funktionen für Loops ableiten. Menschliche Intuition reicht für triviale Fälle mit kleinen Schleifen, aber realistisch, komplexe Programme schnell hartnäckige werden.

Erstens, warum sagen Sie „Programme nicht bewiesen werden kann“?

Was meinst du mit "Programme" überhaupt?

Wenn durch Programme sind Sie Algorithmen was bedeutet, wissen Sie nicht, Kruskals? Dijkstra? MST? Prim? Binäre Suche? Zusammenführen, sortieren? DP? All diese Dinge haben mathematische Modelle, die ihr Verhalten beschreiben.

DESCRIBE. Math nicht erklären, warum die Dinge es einfach ein Bild von der, wie zieht. Ich kann Ihnen nicht beweisen, dass die Sonne morgen auf den Osten steigen wird, aber ich kann die Daten zeigen, wo es auf der Vergangenheit hat sich gezeigt, dass zu tun.

Sie sagte: „Wenn Sie ein Computerprogramm zu schreiben, wie es ist, dass Sie bereits bewährte Arbeiten übernehmen und nutzen sie, um die Wahrheit des Programms zu zeigen? Sie können nicht, da keine vorhanden ist“

Bitte warten? Sie können nicht? http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis

kann ich Ihnen zeigen, nicht „Wahrheit“ ich ein Programm, so viel wie ich dich nicht „Wahrheit“ auf Sprache zeigen kann. Beide sind Darstellungen der empirischen Verständnis der Welt. Nicht auf „Wahrheit“. Putting alle Kauderwelsch beiseite kann ich Ihnen zeigen, mathematisch, dass ein mergesort algorith die Elemente auf einer Liste mit O (n log n) Leistung sortieren wird, dass ein Dijkstra wird den kürzesten Weg auf einem gewichteten Graphen finden, oder dass Euklids Algorithmus finden Sie die größte gemeinsame Teiler zwischen zwei Zahlen. Die „Wahrheit in meinem Programm“ in diesem letzten Fall vielleicht, dass ich Ihnen den größten gemeinsamen Teiler zwischen zwei Zahlen finde, nicht wahr?

Mit einer Rekursionsgleichung ich Ihnen beschreiben kann, wie Sie Ihr Fibonacci-Programm funktioniert.

Nun ist der Computerprogrammierung eine Kunst? Ich denke, dass es ist. So viel wie Mathematik.

Ich komme nicht aus einem mathematischen Hintergrund, so verzeihen Sie meine Unwissenheit, aber was bedeutet „ein Programm zu beweisen“? Was beweisen Sie? Die Richtigkeit? Die Richtigkeit ist eine Spezifikation, die das Programm überprüfen muß „richtigen“ zu sein. Aber diese Beschreibung wird von einem Menschen entschieden, und wie überprüfen Sie, dass diese Spezifikation ist richtig?

In meinen Augen gibt es Fehler in Programm, weil Menschen Schwierigkeiten haben, das auszudrücken, was sie wirklich wollen. alt text http://www.processdevelopers.com/images/PM_Build_Swing.gif

Also, was beweisen Sie? Bugs verursacht durch Mangel an Aufmerksamkeit?

  

Außerdem, was sind die Axiome der Programmierung? Die sehr atomaren Wahrheiten des Feldes?

Ich habe einen Kurs namens Contract Based Programming (Kurs-Homepage TA'ed: http: // www.daimi.au.dk/KBP2/ ). Hier ist, was ich aus dem Kurs extrapolieren kann (und anderen Kursen, die ich genommen habe)

Sie müssen formal (mathematisch) die Semantik der Sprache definieren. Denken wir an einer einfachen Programmiersprache; eine, die nur globale Variablen hat, Ints, int Arrays, Arithmetik, if-then-else, während, Zuordnung und do-nothing [Sie wahrscheinlich eine Teilmenge aller Mainstream-Sprache als „Umsetzung“ dieser können].

ein Ausführungszustand eine Liste von Paaren (Variablenname, Wert der Variable) wäre. Lesen Sie "{Q1} S1 {Q2}" als "Ausführen Anweisung S1 führt von Ausführungszustand Q1 bis Q2 Zustand".

Ein Axiom würde dann "if both {Q1} S1 {Q2} and {Q2} S2 {Q3}, then {Q1} S1; S2 {Q3}" werden. Das heißt, wenn Anweisung S1 Sie vom Zustand Q1 bis Q2 nimmt, und Anweisung S2 führt von Q2 auf Q3, dann „S1, S2“. (S1, gefolgt von S2) führt vom Zustand Q1 bis Q3 Zustand

Ein weiteres Axiom würde "if {Q1 && e != 0} S1 {Q2} and {Q1 && e == 0} S2 {Q2}, then {Q1} if e then S1 else S2 {Q2}" werden.

Nun, ein bisschen Raffinesse: Die Qn der in {} würde s tatsächlich Aussagen über Zustände, erklärt sich nicht

. Angenommen

, daß M (out, A1, A2) ist eine Aussage, die hat eine Verschmelzung von zwei sortierten Arrays und speichert das Ergebnis in geführt, und alle Worte, die ich im nächsten Beispiel verwenden zum Ausdruck gebracht wurden formal (mathematisch). Dann "{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}" wird der Anspruch tha M korrekt implementiert den Merge-Algorithmus.

kann man versuchen, dies zu beweisen, indem sie die oben genannten Axiome verwendet (ein paar anderen wahrscheinlich erforderlich sein würde. Sie sind wahrscheinlich eine Schleife, für eine benötigen).

Ich hoffe, das zeigt ein wenig von dem, was beweis Programme korrekt aussehen könnte. Und glauben Sie mir: es dauert ein Los die Arbeit, auch für scheinbar einfache Algorithmen, um zu beweisen, sie zu korrigieren. Ich weiß, ich habe eine Menge Versuche lesen; -)

[wenn Sie dies lesen: Ihre Hand-in war in Ordnung, es ist alles die anderen, die mir Kopfschmerzen verursacht werden; -)]

Natürlich können sie, wie andere geschrieben haben.

Proving ein sehr kleines Unterprogramm korrekt ist eine gute Übung, die meine Meinung nach jedem Student in einem Programmierbezogenen Studiengang sollte sein erforderlich zu tun. Es gibt Ihnen einen großartigen Einblick in das Denken darüber, wie Sie den Code klar, leicht überprüfbare und wartbar zu machen.

Doch in der realen Welt ist es von begrenztem praktischem Nutzen.

Zuerst, wie Programme Fehler haben, so mathematische Beweise zu tun. Wie beweist, dass ein mathematischer Beweis wirklich korrekt ist, und hat keine Fehler? Sie können nicht. Und für Gegenbeispiel, eine beliebige Anzahl von veröffentlichten mathematischen Beweisen Fehler gehabt haben in ihnen entdeckt, manchmal Jahre später.

Zweitens können Sie nicht beweisen, dass ein Programm, ohne richtig ist ‚a priori‘ eine eindeutige Definition dessen, was das Programm tun soll. Aber jede eindeutige Definition dessen, was ein Programm tun soll ist ein Programm. (Obwohl es ein Programm in irgendeiner Art von Spezifikationssprache sein kann, dass Sie nicht einen Compiler für haben.) Deshalb, bevor Sie nachweisen können, dass ein Programm korrekt ist, müssen Sie zunächst ein anderes Programm, das äquivalent ist und im Voraus bekannt ist richtig liegen. So QED ist das Ganze sinnlos.

Ich würde empfehlen, das klassische " Nein Silver Bullet " -Artikel von Brooks aufzuspüren.

Theres viel Forschung auf diesem Gebiet .. wie andere gesagt haben, die Konstrukte innerhalb einer Programmsprache sind komplex, und dies wird nur schlimmer, wenn man versucht, für beliebige Eingaben zu bestätigen oder zu beweisen.

Allerdings erlauben viele Sprachen für Spezifikationen, auf welche Eingaben sind zulässig (Voraussetzungen), und ermöglichen auch das Endergebnis (nach Bedingungen) für die Angabe.

Solche Sprachen sind: B, Ereignis B, Ada, Fortran

.

Und natürlich gibt es viele Werkzeuge, die uns zu beweisen, bestimmte Eigenschaften über Programme sollen helfen. Zum Beispiel Deadlock Freiheit zu beweisen, könnte man ihr Programm durch SPIN knirschen.

Es gibt auch viele Tools gibt, die uns Fehler erkennen auch Logik helfen. Dies kann über die statische Analyse (Waran, satabs) oder tatsächliche Ausführung von Code (Gnu valgrind?) Durchgeführt werden.

Es gibt jedoch niemanden Werkzeug, das wirklich erlaubt es, ein ganzes Programm zu beweisen, von der Gründung (Spezifikation), Implementierung und Bereitstellung. Die B-Methode kommt in der Nähe, aber die Umsetzung Überprüfung ist sehr, sehr schwach. (Er geht davon aus, dass der Mensch infalible in der Übersetzung von speicficaiton in implmentation).

Als Randbemerkung, wenn die B-Methode verwenden, werden Sie häufig komplexe Beweise aus kleineren Axiome bauen. (Und das gleiche gilt für andere exhasustive Theorembeweisern).

Sie können. Ich habe viele, viele Stunden als College-Neuling Programm Korrektheitsbeweise zu tun.

Der Grund ist es im Makromaßstab nicht praktisch ist, dass ein Beweis für ein Programm zu schreiben, das Programms viel schwieriger zu sein scheint als das Schreiben. Auch Programmierer heute neigen Systeme zu bauen, nicht schreiben Funktionen oder Programme.

Auf einem Mikromaßstab, ich mache es manchmal geistig für einzelne Funktionen, und neigen dazu, meinen Code zu organisieren, um sie einfach zu machen, um zu überprüfen.

Es gibt einen berühmten Artikel über die Space-Shuttle-Software. Sie haben Beweise, oder etwas Gleichwertiges. Es ist unglaublich teuer und zeitaufwendig. Das Niveau der Überprüfung kann für sie, aber für jede Art von Verbrauchern oder kommerziellen Software-Unternehmen, mit aktuellen Techniken erforderlich sein, werden Sie Ihr Mittagessen von einem Konkurrenten gegessen erhalten, die eine 99,9% ige Lösung bei 1% der Kosten liefert. Niemand wird $ 5000 für eine MS Office zahlen, die geringfügig stabiler ist.

Wenn Sie Vertrauen suchen, ist die Alternative zu beweisen, Programme testen sie. Dies ist leichter zu verstehen und kann automatisiert werden. Es ermöglicht auch die Klasse von Programmen, für die Beweise mathematisch nicht möglich sind, wie oben beschrieben.

Vor allem kein Beweis ist ein Ersatz Abnahmeprüfungen für das Bestehen: *

  • Nur weil ein Programm wirklich tut, was sie sagt, es ist, bedeutet nicht, es tut, was die Nutzer wollen, es zu tun.

    • Es sei denn, Sie können das beweisen, was sie sagt, es tut, ist, was der Benutzer sagt, sie wollen.

      • , die Sie dann unter Beweis stellen müssen, ist, was sie wirklich wollen , weil ein Benutzer sein, sie mit ziemlicher Sicherheit nicht wissen, was sie wollen. usw. ad absurdum.

* nicht zu erwähnen Einheit, Netzabdeckung, funktionelle, Integration und alle anderen Arten von Tests.

Hope this Sie auf Ihrem Weg hilft.

Etwas, das hier nicht erwähnt hat, ist die B - Methode , die a formale Methode basierendes System. Es wurde verwendet, um das Sicherheitssystem der Pariser U-Bahn zu entwickeln. Es gibt Tools zur Verfügung, B und Ereignis B Entwicklung zu unterstützen, insbesondere Rodin .

Sie können nicht nur Programme beweisen, können Sie Ihre Computerprogramme von Proofs konstruieren lassen. Siehe Coq . Sie brauchen also nicht einmal über die Möglichkeit zu befürchten haben, einen Fehler in der Implementierung gemacht zu haben.

Gödels Theoreme trotz ... Was wäre der Punkt ? Was simpel „Wahrheiten“ würden Sie beweisen möchte? Was würden Sie wollen aus diesen Wahrheiten abzuleiten? Während ich diese Worte essen kann ... wo ist die Praktikabilität?

Programme können nachgewiesen werden. Es ist ruhig einfach, wenn man sich in der Sprache schreiben, wie zum Beispiel Standard ML von New Jersey (SML / NJ).

Ihre Aussage ist breit, so dass es viele Fische zu fangen.

Das Endergebnis ist: einige Programme auf jeden Fall richtig nachgewiesen werden kann. Alle Programme können nicht korrekt nachgewiesen werden.

Hier ist ein triviales Beispiel die, Geist, Sie ist genau die gleiche Art von Beweis, dass settheorie wieder in den Tag zerstört: ein Programm machen, das feststellen kann, ob sich korrekt ist, und wenn er feststellt, dass es ist richtig, eine falsche Antwort geben.

Dies ist Gödels Satz, schlicht und einfach.

Das ist aber nicht so problematisch, da wir viele Programme unter Beweis stellen können.

Lassen Sie uns eine rein funktionale Sprache (dh Haskell) annehmen. Nebenwirkungen ganz sauber berücksichtigt werden können in solchen Sprache gemacht.

Der Beweis, dass ein Programm, das richtige Ergebnis erzeugt erfordert Sie angeben:

  1. eine Entsprechung zwischen Datentypen und mathematischen Sätzen
  2. eine Entsprechung zwischen Haskell Funktionen und mathematischen Funktionen
  3. eine Menge von Axiomen spezifizieren, welche Funktionen Sie von anderen zu bauen sind erlaubt, und die entsprechende Konstruktion auf der mathematischen Seite.

Dieser Satz von Spezifikationen heißt denotational Semantik . Sie ermöglichen es, den Grund zu Programmen mit Mathematik zu beweisen.

Die gute Nachricht ist, dass die „Struktur der Programme“ (Punkt 3 oben) und die „Struktur der mathematischen Sätze“ sehr ähnlich sind (das Schlagwort ist Topos oder kartesischer Kategorie geschlossen ), so 1 / die Beweise Sie auf der Mathe Seite tun wird leicht in programmatischen Konstruktionen 2 / die Programme übertragen werden Sie schreiben, sind leicht gezeigt werden, um mathematisch korrekt.

Lesen Sie auf dem Halteproblem (die über die Schwierigkeit ist etwas so einfach zu beweisen, als ob ein Programm abgeschlossen ist oder nicht). Im Grunde ist das Problem im Zusammenhang mit Gödels Unvollständigkeitssatz.

Einige Teile können von Programmen nachgewiesen werden. Zum Beispiel kann der C # -Compiler, die statisch überprüfen und Typsicherheit gewährleisten, wenn die die Kompilierung erfolgreich ist. Aber ich vermute, der Kern Ihrer Frage zu beweisen, dass ein Programm korrekt ausführt. Viele (ich wage nicht zu sagen die meisten) Algorithmen nachgewiesen werden können, richtig, aber ein ganzes Programm wahrscheinlich nachgewiesen werden kann, nicht statisch auf den folgenden Ursachen zurückzuführen sein:

  • erfordert Überprüfung aller möglichen Zweige (Anrufe, ifs und interupts) durchlaufen werden, die im erweiterten Programmcode hat super-cubic Zeitkomplexität (daher wird es nie vollständig innerhalb einer angemessenen Zeit).
  • Einige Programmiertechniken, entweder durch Komponenten herstellen oder mithilfe von Reflektion, macht es unmöglich, statisch Ausführung von Code zur Vorhersage (dh Sie wissen nicht, wie ein anderer Programmierer Ihre Bibliothek verwenden, und die Compiler hat eine harte Zeit vorhersagen, wie Reflexion in ein Verbraucher Funktionalität aufrufen.

Und das sind nur einige ...

Wenn das Programm verfügt über eine gut definiertes Ziel und Ausgangsannahmen (ohne Berücksichtigung von Gödel ...) nachgewiesen werden kann. Suche alle Primzahlen, x, für 6 <= x <= 10, Ihre Antwort ist 7 und dass nachgewiesen werden kann. Ich schrieb ein Programm, die NIM spielt (das erste Python-Programm ich schrieb auch immer) und in der Theorie gewinnt der Computer immer nach dem Spiel in einen Zustand fällt, in dem der Computer gewinnen. Ich habe nicht in der Lage gewesen, es als wahr zu beweisen, aber es ist wahr (mathematisch durch einen digitalen binäre Summe Beweis) Ich glaube, es sei denn ich einen Fehler im Code. Habe ich einen Fehler machen, nicht ernst, kann mir jemand sagen, ob dieses Programm schlagbar ist?

Es gibt einige mathematische Sätze, die „bewiesen“ mit Computercode wie der Vierfarbensatz wurden . Aber es gibt Einwände, weil, wie Sie gesagt haben, können Sie das Programm unter Beweis stellen?

  

Außerdem, was sind die Axiome der Programmierung? Die sehr atomaren Wahrheiten des Feldes?

Sind die Opcodes die "Atom-Wahrheiten"? Zum Beispiel beim Anblick ... 

mov ax,1

... könnte keinen Programmierer behauptet als selbstverständlich, dass ein Hardwareproblem Sperre, nach der Ausführung dieser Anweisung der ax Register der CPU jetzt 1 enthalten würde?

  

Wenn Sie ein Computerprogramm zu schreiben, wie es ist, dass Sie bereits bewährte Arbeiten übernehmen und nutzen sie, um die Wahrheit des Programms zu zeigen?

Die „bisherige Arbeit“, dann könnte die Laufzeitumgebung, in der das neue Programm ausgeführt wird.

Das neue Programm kann nachgewiesen werden. Neben den formalen Beweisen, kann es „durch Inspektion“ nachgewiesen werden und durch verschiedene Formen der „Prüfung“ (einschließlich „Abnahmeprüfung“)

  

Wie beweisen Sie einen Picasso?

Wenn Software mehr wie Industriedesign oder Ingenieurwissenschaften als wie Kunst ist, eine bessere Frage könnte sein, „wie man eine Brücke unter Beweis stellen, oder ein Flugzeug?“

ein Programm erweist sich richtig kann nur relativ des Programms der Spezifikation durchgeführt werden; es ist möglich, aber teuer / zeitaufwendig

einige CASE-Systeme produzieren Programme zugänglicher Beweise als andere - aber wieder, dies beruht auf einer formalen Semantik der Spezifikation ...

... und so wie beweisen Sie die Spezifikation richtig? Richtig! Mit mehr Spezifikationen!

Ich lese ein wenig über das, aber es gibt zwei Probleme.

Erstens können Sie nicht etwas abstraktes Ding beweisen genannt Richtigkeit. Sie können, wenn die Dinge richtig eingerichtet sind, beweisen, dass zwei formale Systeme gleichwertig sind. Sie können beweisen, dass ein Programm eine Reihe von Spezifikationen implementiert, und es ist am einfachsten, dies zu tun, indem Sie den Beweis und Programm mehr oder weniger parallel zu konstruieren. Daher müssen die Spezifikationen detailliert genug sein, etwas zu schaffen, gegen zu beweisen, und daher die Spezifikation ist effektiv ein Programm . Das Problem der das Schreiben eines Programms einen Zweck wird das Problem einer formalen detaillierte Spezifikation eines Programms zu erfüllen, schreiben einen Zweck zu erfüllen, und das ist nicht unbedingt ein Schritt nach vorn.

Zweitens sind Programme kompliziert. So sind Beweise für die Richtigkeit. Wenn Sie einen Fehler ein Programm schreiben, machen können, können Sie sicher einen beweis machen. Dijkstra und Gries hat mir gesagt, im Wesentlichen, dass, wenn ich ein perfekter Mathematiker bin ich ein guter Programmierer sein könnte. Der Wert ist hier, dass zu beweisen und Programmierung sind zwei etwas andere Denkprozesse, und zumindest in meiner Erfahrung, die ich mache verschiedene Arten von Fehlern.

Nach meiner Erfahrung Programme beweisen, ist nicht nutzlos. Wenn ich versuche, etwas zu tun, ich formal beschreiben kann, beweisen die Implementierung korrekt beseitigt eine ganze Menge schwer zu finden Fehler, vor allem die Dummen zu verlassen, die ich leicht in der Prüfung fangen. Bei einem Projekt, das extrem fehlerfreien Code erzeugen muss, kann es eine sinnvolle Ergänzung sein. Es ist nicht für jede Anwendung geeignet, und es ist sicherlich kein Allheilmittel.

Wie andere darauf hingewiesen, (einige) Programme in der Tat nachgewiesen werden können.

Ein Problem jedoch in der Praxis ist, dass müssen Sie zuerst etwas (das heißt eine Annahme oder Satz), die Sie wollen beweisen. So etwas über ein Programm zu beweisen, dass Sie zunächst eine formale Beschreibung brauchen, was es tun soll (beispielsweise vor und nach Bedingungen).

Mit anderen Worten, müssen Sie eine formale Spezifikation des Programms. Aber immer noch eine vernünftige (und noch weniger eine strenge formale) Spezifikation ist bereits eines der schwierigsten Dinge in der Softwareentwicklung. Daher ist es in der Regel sehr schwierig zu beweisen, interessant Dinge über ein (reales) Programm.

Es gibt jedoch einige Dinge, die (und haben) sein können leichter formalisiert (und bewährten). Wenn Sie zumindest nachweisen können, dass Ihr Programm wird nicht abstürzen, das ist schon etwas: -).

BTW, einige Compiler-Warnungen / Fehler sind im Wesentlichen (einfach) Beweise über ein Programm. Z. B. werden die Java-Compiler unter Beweis stellen, dass Sie nie eine nicht initialisierte Variable im Code zugreifen (sonst wird es Ihnen einen Compiler-Fehler geben).

Ich habe nicht Lesen Sie alle Antworten, aber die Art, wie ich es sehe, beweisen Programme ist sinnlos, das ist, warum tut es niemand.

Wenn Sie haben eine relativ kleine/medium-Projekt (sagen, 10K Zeilen code), dann der Beweis ist wahrscheinlich gonna werden auch 10k Zeilen, wenn nicht länger.

Denken über es, wenn das Programm kann Fehler haben, der Nachweis kann auch "bugs".Vielleicht benötigen Sie einen Beweis für den Beweis!

Eine andere Sache zu prüfen, Programme sind sehr sehr formal und präzise sein.Sie können nicht mehr streng und formal, da der Programm-code, der ausgeführt werden soll, durch eine dumme Maschine.

Während die Beweise gehen, zu Lesen von Menschen, so dass Sie in der Regel weniger streng sind als der eigentliche code.

Die einzigen Dinge, die Sie ll wollen, um zu beweisen, sind low-level-algorithmen, die auf bestimmte Datenstrukturen (z.B.quicksort, einfügen in einen binären Baum, etc).

Diese Dinge sind etwas kompliziert, es ist nicht sofort offensichtlich, warum Sie arbeiten, und/oder ob Sie immer funktioniert.Sie sind auch die grundlegenden Bausteine für alle andere software.

Die meisten Antworten auf die Praxis konzentrieren und das ist in Ordnung: in der Praxis Sie kümmern sich nicht um formale Proofing. Aber was ist in der Theorie?

Die Programme können nur als eine mathematische Aussage kann nachgewiesen werden. Aber nicht in dem Sinne, Sie gemeint! In jedem ausreichend leistungsfähigen Rahmen, gibt es mathematische Aussagen (und Programme), die nachgewiesen werden können, nicht! Siehe hier

So viel Lärm hier, aber ich werde jedenfalls in den Wind schreien ...

„als richtig erweist“ hat verschiedene Bedeutungen in verschiedenen Kontexten. In formalen Systeme „als richtig“ bedeutet, dass eine Formel aus anderen abgeleitet werden kann, bewiesen (oder axiomatischen ) Formeln. „Beweisen Sie richtig“ in der Programmierung einfach Code zeigt, entspricht einer formalen Spezifikation zu sein. Aber wie beweist man die formale Spezifikation richtig? Leider gibt es keine Möglichkeit, eine Spezifikation zu zeigen, fehlerfrei oder eine Lösung für jedes reales Problem anders als durch Tests sein.

Just my 2 cents, die interessanten Sachen Zugabe schon da.

Von allen Programmen, die nicht bewiesen werden kann, die häufigsten diejenigen Durchführung IO (einige unpredictible Interaktion mit der Welt oder den Benutzer). Auch automatische Beweise manchmal einfach vergessen, dass „bewährte“ Programme“auf einigen physischen Hardware laufen, nicht die ideale ein durch das Modell beschrieben.

Auf der anderen Seite mathematische Beweise kümmern sich nicht viel von der Welt. Eine wiederkehrende Frage mit Mathe ist, wenn es etwas Reales beschreibt. Es ist jedes Mal etwas Neues wie imaginäre Zahlen angehoben oder nicht-euklidischen Raum erfunden. Dann wird die Frage vergessen, wie diese neuen Theorien so gute Werkzeuge sind. Wie ein gutes Programm, es funktioniert einfach.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top