Warum können Programme nicht nachgewiesen werden?
Warum kann nicht ein computer-Programm nachgewiesen werden, ebenso wie eine mathematische Aussage kann? Ein mathematischer Beweis aufgebaut ist, auf andere Beweise, die aufgebaut werden, von noch mehr Beweise und auf nach unten, um Axiome - diese Wahrheiten Wahrheiten halten wir als selbstverständlich.
Computer-Programme nicht zu haben scheinen eine solche Struktur. Wenn Sie schreiben ein computer-Programm, wie kommt es, dass Sie nehmen können bisherige bewährte Werke und verwenden Sie Sie, um zu zeigen, die Wahrheit von deinem Programm? Sie können nicht, da keine vorhanden sind. Weiter, was sind die Axiome der Programmierung? Die sehr atomic Wahrheiten des Feldes?
Ich keine guten Antworten auf die oben genannten. Aber es scheint-software kann nicht bewiesen werden, weil es Kunst ist und keine Wissenschaft. Wie beweist man einen Picasso?
InformationsquelleAutor der Frage |
Du musst angemeldet sein, um einen Kommentar abzugeben.
Beweise sind Programme.
Formale Verifikation von Programmen ist ein riesige Fachgebiet. (Siehe, zum Beispiel, die Gruppe an der Carnegie Mellon.)
Viele komplexe Programme verifiziert worden sind; zum Beispiel finden Sie in diesem kernel wurde in Haskell geschrieben.
InformationsquelleAutor der Antwort
Programme absolut kann nachgewiesen werden, um korrekt zu sein. Miese Programme sind schwer zu beweisen. Es zu tun, sogar Recht gut, Sie haben sich zu entwickeln das Programm und der Nachweis der hand-in-hand.
Können Sie nicht automatisieren der Beweis, weil der das Halteproblem. Sie können jedoch auch manuell belegen die post-Bedingungen und Voraussetzungen von jedem beliebigen Anweisung oder Anweisungsfolge.
Müssen Sie Lesen Dijsktra ist Eine Disziplin der Programmierung.
Dann müssen Sie Lesen Gries' Die Wissenschaft von der Programmierung.
Dann werden Sie wissen, wie um zu beweisen, Programme korrigieren.
InformationsquelleAutor der Antwort
Nur eine kleine Anmerkung für diejenigen, die erzogen Unvollständigkeit-es ist nicht der Fall für alle axiomatische Systeme, nur mächtig genug lieben.
In anderen Worten, Gödel bewiesen, dass eine axiomatische system leistungsfähig genug, um zu beschreiben wäre zwangsläufig unvollständig sein. Dies bedeutet nicht, es wäre jedoch nutzlos, und, wie andere verlinkt haben, verschiedene versuche, das Programm Beweise gemacht worden.
Dem dualen problem (das schreiben von Programmen zu prüfen, die Beweise) ist auch sehr interessant.
InformationsquelleAutor der Antwort
Das Halteproblem zeigt nur, dass es Programme gibt, die nicht verifiziert werden können. Einem viel mehr interessante und praktische Frage ist, welche Klasse von Programmen kann formal verifiziert. Vielleicht jedes Programm jemand darum kümmert könnte (in der Theorie) überprüft werden.
In der Praxis bisher nur sehr kleine Programme, die erwiesen haben, zu korrigieren.InformationsquelleAutor der Antwort
Können Sie in der Tat schreiben, die nachweisbar richtigen Programme. Microsoft, zum Beispiel, hat eine Erweiterung der Sprache C# genannt Spezifikation# umfasst eine automatisierte theorembeweiser. Für java gibt es ESC/java. Ich bin sicher, es gibt viele weitere Beispiele gibt.
(Bearbeiten: offenbar spec# ist nicht mehr entwickelt, aber der Vertrag tools werden .NET 4.0)
Sehe ich einigen Plakaten winken mit den Händen über die Halteproblem oder Unvollständigkeit Theoremedie angeblich verhindern, dass die automatische Verifikation von Programmen. Dies ist natürlich nicht wahr; diese Dinge lediglich zu sagen, dass es möglich, Programme zu schreiben, die noch nicht nachgewiesen werden richtige oder falsche. Das hindert uns nicht daran, den Bau Programme, die sind nachweislich korrekt.
InformationsquelleAutor der Antwort
Wenn du wirklich Interesse an der Thematik, lassen Sie mich zuerst empfehlen David Gries "The Science of Programming", ein Klassiker der einführenden Arbeit am Thema.
Es tatsächlich möglich ist, beweisen Programme einigermaßen stimmt. Sie können schreiben, Vorbedingungen und nachbedingungen und dann beweisen, dass Sie in einem gegebenen Zustand, der erfüllt die Voraussetzungen, die daraus resultierende Zustand nach Ausführung entsprechen die nachbedingungen.
Wo es schwierig wird, jedoch ist Schleifen. Für diese, benötigen Sie (zusätzlich zu finden, ein loop-invariant und zeigen einen korrekten Abschluss, müssen Sie eine Obere Schranke der Funktion auf der maximal möglichen Anzahl der Iterationen, die übrigen nach jeder Schleife. Sie müssen auch in der Lage sein zu zeigen, dass dieser Rückgang durch mindestens eine der nach jeder iteration der Schleife.
Wenn Sie alle diese für ein Programm, der Beweis ist mechanisch. Aber leider gibt es keine Möglichkeit, automatisch die Ableitung der Invarianten gebunden und Funktionen for-Schleifen. Die menschliche intuition genügt für triviale Fälle mit kleinen Schleifen, aber realistisch gesehen, auch komplexe Programme schnell zu bewältigen.
InformationsquelleAutor der Antwort
Erstens, warum sagen Sie "Programme KÖNNEN NICHT nachgewiesen werden"?
Was meinst du mit "Programme" überhaupt?
Wenn durch Programme, die Sie sind Bedeutung, algorithmen, wissen Sie nicht, Kruskal ' s? Dijkstra? MST? Prim ist? Binäre Suche? Mergesort? DP? All diese Dinge haben mathematische Modelle, die beschreiben, Ihre Verhaltensweisen.
BESCHREIBEN. Mathematik erklärt nicht das warum der Dinge, ist es einfach zeichnet ein Bild von der, wie. Ich kann nicht beweisen, dass die Sonne morgen über den Osten, aber ich kann zeigen die Daten, wo Sie es getan hat, die Sache auf die Vergangenheit.
Sagte Sie:
"Wenn Sie schreiben ein computer-Programm, wie kommt es, dass Sie nehmen können bisherige bewährte Werke und verwenden Sie Sie, um zu zeigen, die Wahrheit von deinem Programm? Sie können nicht, da keine vorhanden sind"
Warten? KÖNNEN Sie das NICHT?
http://en.wikipedia.org/wiki/Algorithm#Algorithmic_analysis
Kann ich nicht zeigen Sie "die Wahrheit" habe ich ein Programm so viel wie ich kann nicht zeigen Sie "die Wahrheit" über die Sprache. Beide Darstellungen unserer empirischen Verständnis von der Welt. Nicht auf "Wahrheit". Alles Quatsch beiseite, ich kann zeigen Sie rechnerisch, dass ein mergesort algorith Sortieren der Elemente einer Liste mit O(nlogn) - performance, die ein Dijkstra-werden den kürzesten Weg zu finden, die auf einer gewichteten Graphen, oder, dass Euklid ' s Algorithmus finden Sie den größten gemeinsamen Teiler zwischen zwei zahlen. Die "Wahrheit in meinem Programm" in diesem letzten Fall vielleicht, dass ich werde finden Sie den größten gemeinsamen Teiler zwischen zwei zahlen, meinst du nicht?
Mit einem Rezidiv Gleichung kann ich umreißen, wie Sie Ihre Fibonacci-Programm funktioniert.
Nun, der computer-Programmierung eine Kunst? Ich denke, es ist. So viel wie die Mathematik.
InformationsquelleAutor der Antwort
Ich komme nicht aus einer mathematischen hintergrund, so verzeihen Sie meine Unwissenheit, aber was bedeutet "zu beweisen, ein Programm"?
Was du zu beweisen? Die Richtigkeit? Die Richtigkeit ist eine Spezifikation, muss das Programm überprüfen, um "korrigieren". Aber diese Angabe wird entschieden, von einem Menschen, und wie überprüfen Sie, dass diese Angabe korrekt ist?
Meiner Meinung nach gibt es Fehler im 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 sollen Sie beweisen? Fehler, verursacht durch mangelnde Aufmerksamkeit?
InformationsquelleAutor der Antwort
Ich hab 'ed TA einen Kurs namens" Vertrag Basierte Programmierung (Kurs-homepage: http://www.daimi.au.dk/KBP2/). Hier, was ich kann extrapolieren aus dem Kurs (und andere Kurse, die ich belegt habe)
Müssen Sie formal (mathematisch) bestimmen Sie die Semantik der Sprache ist. Wir denken, eine einfache Programmiersprache, eine, Globale Variablen int, int-arrays, Arithmetik, if-then-else, while -, Zuweisungs-und do-nothing [können Sie wahrscheinlich verwenden eine Teilmenge von jedem mainstream-Sprache als eine "Umsetzung" dieser].
Ausführung-Staat wäre eine Liste von Paaren (Variablenname, Wert der variable). Lesen Sie "{Q1} S1 {Q2}" als "ausführende Anweisung S1 bringt Sie von der Ausführung Zustand Q1 auf Zustand Q2".
Einem axiom würde dann
"if both {Q1} S1 {Q2} and {Q2} S2 {Q3}, then {Q1} S1; S2 {Q3}". Das ist, wenn-Anweisung S1 bringt Sie aus dem Zustand Q1 zu Q2 und Anweisung S2 führt Sie von Q2 auf Q3, dann "S1; S2" (S1 gefolgt von S2) führt von Zustand Q1 auf Zustand Q3.Einem anderen axiom wäre
"if {Q1 && e != 0} S1 {Q2} and {Q1 && e == 0} S2 {Q2}, then {Q1} if e then S1 else S2 {Q2}".Nun, ein bisschen verfeinert: die Qn in {}'s wäre eigentlich Aussagen über Staaten, nicht Staaten selbst.
Angenommen, dass M(A1, A2) ist eine Aussage, die nicht Zusammenführen von zwei sortierten arrays und speichert das Ergebnis in out, und alle Worte, die ich verwenden im nächsten Beispiel äußert der formal (mathematisch). Dann
"{sorted(A1) && sorted(A2)} A := M(A1, A2) {sorted(A) && permutationOf(A, A1 concatened with A2)}"ist der Anspruch tha M korrekt implementiert die merge-Algorithmus.Kann man versuchen, dies zu beweisen, indem Sie mithilfe der obigen Axiome (und ein paar andere würden wohl nötig sein. Sie sind wahrscheinlich zu müssen, um eine Schleife, die for-one).
Ich hoffe das verdeutlicht ein wenig was beweisen, Programme korrigieren Aussehen könnte. Und glauben Sie mir: es dauert eine viel Arbeit, auch für scheinbar einfache algorithmen, um zu beweisen, dass Sie korrekt sind. Ich weiß, ich lese viel versucht 😉
[wenn Sie dies Lesen: Ihre hand-in war in Ordnung, es ist all die anderen, das verursacht mir Kopfschmerzen ;-)]
InformationsquelleAutor der Antwort
Natürlich können Sie, wie andere geschrieben haben.
Beweisen, dass es ein sehr kleines Unterprogramm zu korrigieren ist eine gute übung, die IMHO alle Studierenden in Programmier-bezogenen Studiengang sollte erforderlich zu tun. Es gibt Ihnen einen tollen Einblick in das denken darüber, wie Sie Ihre code-klare, leicht nachvollziehbare und vertretbare.
Jedoch in der realen Welt ist es von begrenztem praktischen nutzen.
Erste, nur als Programme haben bugs, so haben mathematische Beweise. Wie kann beweisen, dass ein mathematischer Beweis ist wirklich richtig und hat keine Fehler? Das können Sie nicht. Und für counter-Beispiel, eine beliebige Anzahl von veröffentlichten mathematische Beweise gehabt haben, Fehler entdeckt in Ihnen, manchmal Jahre später.
Zweitens, Sie können nicht beweisen, dass ein Programm korrekt ist, ohne 'a priori', die eine eindeutige definition dessen, was das Programm tun soll. Aber eine eindeutige definition, was ein Programm tun soll, ist ein Programm. (Obwohl es sein kann ein Programm in eine Art Spezifikation der Sprache, dass Sie nicht einen compiler für.) Daher, bevor Sie beweisen können, dass ein Programm korrekt ist, müssen Sie zunächst ein anderes Programm, das gleichwertig ist und im Voraus bekannt ist, um korrekt zu sein. Also QED ist die ganze Sache zwecklos.
Ich würde empfehlen, das aufspüren des klassischen "Keine Silberne Kugel" Artikel von Brooks.
InformationsquelleAutor der Antwort
Theres viel Forschung in diesem Bereich.. wie schon andere gesagt haben, die Konstrukte, die innerhalb einer Sprache sind Komplex, und das wird nur schlimmer, wenn Sie versuchen, zu überprüfen oder beweisen Sie für beliebige Eingaben.
Jedoch, viele Sprachen erlauben für Spezifikationen, auf welche Eingänge sind zulässig (Voraussetzungen), und auch für die Angabe der Ende-Ergebnis (post-conditions).
Solche Sprachen sind: B, Fall B, Ada, fortran.
Und natürlich, es gibt viele Werkzeuge, die entworfen sind, um uns zu helfen, beweisen Sie bestimmte Eigenschaften über Programme. Zum Beispiel, um zu beweisen, deadlock-Freiheit , könnte man crunch Ihrem Programm durch DREHEN.
Es gibt auch viele tools gibt, die auch helfen, uns erkennen, die Logik-Fehler. Diese kann getan werden, über die statische Analyse (goanna, satabs) oder tatsächliche Ausführung von code (valgrind gnu?).
Es ist jedoch keine one-tool, das wirklich erlaubt zu beweisen, ein ganzes Programm, von der Gründung (Konkretisierung), Umsetzung und Bereitstellung. Die B-Methode sehr nahe kommt, aber seine Umsetzung ist eine Kontrolle sehr sehr schwach. (Es wird davon ausgegangen, dass der Mensch infalible in der übersetzung von speicficaiton in-Implementierung).
Als Seite beachten, wenn mit Hilfe der B-Methode, Sie werden Häufig finden sich Gebäude Komplex Beweise aus kleineren Axiome. (Und das gleiche gilt für andere exhasustive theorembeweiser).
InformationsquelleAutor der Antwort
Können Sie. Ich verbrachte viele, viele Stunden, wie ein college-Neuling zu tun Programm-Korrektheit beweisen.
Dem Grund ist es nicht praktisch, auf einer makro-Skala ist, dass das schreiben ein Beweis für ein Programm neigt dazu, viel schwerer als schreiben die Programm. Auch die Programmierer von heute neigen dazu, Systeme zu bauen, nicht schreiben, Funktionen oder Programme.
Auf eine Mikro-Skala, manchmal mache ich es mental für einzelne Funktionen, und neigen dazu, den code zu organisieren, um Sie einfach zu überprüfen.
Es gibt einen berühmten Artikel über die space-shuttle-software. Tun Sie Beweise, oder etwas vergleichbares. Es ist unglaublich teuer und zeitaufwendig. Das Niveau der Prüfung kann erforderlich sein, für Sie, sondern für jede Art von Verbraucher-oder kommerzielle software-Unternehmen, mit aktuellen Techniken, erhalten Sie Ihr Mittagessen gegessen von einem Mitbewerber, liefert eine 99,9% ige Lösung in 1% der Kosten. Niemand wird zu zahlen $5000 für ein MS-Office-das ist unwesentlich mehr stabil.
InformationsquelleAutor der Antwort
Wenn Sie auf der Suche für das Vertrauen, die alternative ist, zu beweisen, dass Programme zu testen. Dies ist einfacher zu verstehen und automatisiert werden können. Es ermöglicht auch die Klasse der Programme, für die Beweise sind mathematisch nicht möglich, wie oben beschrieben.
Vor allem kein Beweis dafür ist ein Ersatz für die übergabe-acceptance-tests:*
Nur weil ein Programm wirklich tut, tun, was es sagt, es tut, bedeutet nicht, es tut was der Benutzer will, zu tun.
Es sei denn können Sie beweisen, dass das, was es sagt es tut, ist, was der Benutzer sagt, dass Sie wollen.
*nicht zu erwähnen, Einheit, Abdeckung, Funktions -, Integrations-und alle anderen Arten von tests.
Hoffe, dies hilft Ihnen auf Ihrem Weg.
InformationsquelleAutor der Antwort
Etwas, was noch nicht erwähnt wurde hier ist die B - Methode die eine formale Methode basierten system. Es wurde verwendet, um das Sicherheitssystem der Pariser U-Bahn.
Gibt es tools zur Unterstützung von B-und Event-B Entwicklung, insbesondere Rodin.
InformationsquelleAutor der Antwort
Nicht nur können Sie beweisen, Programme, können Sie lassen Sie Ihren computer konstruieren von Programmen aus beweisen. Sehen Coq. So brauchen Sie sich nicht einmal Gedanken über die Möglichkeit gemacht zu haben einen Fehler in Ihrer Implementierung.
InformationsquelleAutor der Antwort
Gödel-Theoreme trotz...Was würde der Punkt sein? Was simpel "Wahrheiten" möchten Sie beweisen? Was möchten Sie leiten sich von diesen Wahrheiten? Während ich esse diese Worte...wo ist die Sachlichkeit?
InformationsquelleAutor der Antwort
Programme nachgewiesen werden KANN. Es ist ruhig einfach, wenn Sie schreiben Sie in der Sprache wie zum Beispiel Standard ML of New Jersey (SML/NJ).
InformationsquelleAutor der Antwort
Deine Aussage ist so weit es geht, fangen viele Fische.
In der unteren Zeile ist: einige Programme können auf jeden Fall als richtig erwiesen. Alle Programme können nicht als richtig erwiesen werden.
Hier ist ein triviales Beispiel, die, wohlgemerkt, ist genau die gleiche Art von Beweis, dass zerstört-set-Theorie zurück in den Tag: stellen Sie ein Programm, das feststellen kann, ob sich richtig ist, und wenn er feststellt, dass es ist korrigieren, geben eine falsche Antwort.
Dies ist Gödel ' s theorem, schlicht und einfach.
Aber das ist nicht so problematisch, da wir beweisen können viele Programme.
InformationsquelleAutor der Antwort
Lassen Sie uns annehmen, eine rein funktionale Sprache (also Haskell). Nebenwirkungen können durchaus sauber Berücksichtigung der in diesen Sprachen.
Beweisen, dass ein Programm produziert, das Ergebnis erfordert die Angabe:
Dieser Satz von Spezifikationen genannt denotational Semantik. Sie ermöglichen es, zu beweisen, dass die Vernunft über die Programme mit Hilfe der Mathematik.
Die gute Nachricht ist, dass die "Struktur der Programme" (Punkt 3 oben) und die "Struktur mathematischer Sätze" sind ziemlich ähnlich (das Schlagwort ist toposoder kartesischen geschlossen Kategorie), so dass 1/die Beweise, die Sie auf der Mathe-Seite wird leicht übertragen werden, in programmgesteuerten Konstruktionen 2/die Programme, die Sie schreiben werden leicht gezeigt werden mathematisch korrekt.
InformationsquelleAutor der Antwort
Lesen, auf die Halteproblem (das ist in etwa die Schwierigkeit, zu beweisen, etwas so einfaches wie, ob ein Programm beendet ist oder nicht). Grundsätzlich liegt das problem bei Gödel ' s theorem der Unvollständigkeit.
InformationsquelleAutor der Antwort
Einige Teile von Programmen bewiesen werden kann. Zum Beispiel der C# - compiler, die statisch überprüfen und Garantie geben Sicherheit, wenn die Kompilierung erfolgreich ist.
Aber ich vermute, der Kern Ihrer Frage ist zu beweisen, dass ein Programm ordnungsgemäß ausgeführt werden. Viele (ich wage nicht zu sagen die meisten), die algorithmen sein können, erwies sich als richtig, aber ein ganzes Programm wahrscheinlich nicht bewiesen werden statisch durch die folgenden:
Und das sind nur einige...
InformationsquelleAutor der Antwort
Wenn das Programm hat eine gut definierte Ziel und die ursprünglichen Annahmen (ignorieren, Gödel...) nachgewiesen werden kann. Finden Sie alle Primzahlen x, für 6<=x<=10, Ihre Antwort ist 7, und das nachgewiesen werden kann. Ich schrieb eine Programm, das spielt NIM (die ersten Python-Programm, das ich jemals schrieb) und in der Theorie der computer immer gewinnt, nach dem Spiel fällt in einen Zustand, in dem Sie den computer gewinnen können. Ich habe nicht in der Lage, es zu beweisen, wie wahr, aber es IST wahr (mathematisch durch eine digitale binäre Summe Nachweis) ich glaube, es sei denn, ich machte einen Fehler im code. Hab ich einen Fehler machen, Nein, im ernst, kann mir jemand sagen, ob dieses Programm ist schlagbar?
Gibt es einige mathematische Theoreme, die bereits "bewiesen" mit den computer-code wie die vier-Farben-theorem. Aber es gibt auch Einwände, weil, wie Sie sagte, können Sie beweisen, das Programm?
InformationsquelleAutor der Antwort
Sind die opcodes die "atomic Wahrheiten"? Zum Beispiel auf sehen ...
... vielleicht ein Programmierer nicht geltend machen, wie von selbst, dass, abgesehen von ein hardware-problem, nach Ausführung dieser Anweisung der CPU
axregister enthalten jetzt1?Die "früheren arbeiten" dann könnte der run-time-Umgebung, in der das neue Programm läuft.
Des neuen Programms nachgewiesen werden kann: abgesehen von der formalen Beweise, es kann nachgewiesen werden "durch die Prüfung" und durch verschiedene Formen der "Prüfung" (einschließlich der "Abnahme").
Wenn die software mehr wie industrial design oder in der Technik, als wie in der Kunst, eine bessere Frage könnte sein: "wie beweisen Sie, eine Brücke oder ein Flugzeug?"
InformationsquelleAutor der Antwort
beweisen, dass es ein Programm korrekt ist kann nur durchgeführt werden, bezogen auf die Vorgabe des Programms; es ist möglich, aber teuer/zeitaufwendig
einige Systeme produzieren Programme mehr zugänglich Beweise als die anderen - aber, wieder, diese stützt sich auf eine formale Semantik der Spezifikation...
...und so wie du das beweisen die Spezifikation korrekt? Richtig! Mit mehr Spezifikationen!
InformationsquelleAutor der Antwort
Lese ich ein wenig über dieses, aber es gibt zwei Probleme.
Ersten, die Sie nicht beweisen können einige abstrakte Ding namens Korrektheit. Sie können, wenn die Dinge ordnungsgemäß eingerichtet sind, beweisen, dass zwei formale Systeme sind gleichwertig. Können Sie beweisen, dass ein Programm implementiert eine Reihe von Spezifikationen, und es ist am einfachsten dies tun, indem er den Beweis und Programm mehr oder weniger parallel. Also, die Spezifikationen müssen hinreichend detailliert sein, um etwas zu beweisen, gegen, und daher die Spezifikation ist effektiv ein Programm. Das problem des Schreibens eines Programms zu erfüllen einen Zweck wird das problem des Schreibens eine detaillierte formale Spezifikation für ein Programm erfüllen einen Zweck, und das ist nicht unbedingt ein Schritt nach vorne.
Zweitens, die Programme sind kompliziert. So sind Beweise der Richtigkeit. Wenn Sie einen Fehler machen, schreiben Sie ein Programm, die Sie sicher machen kann man beweisen. Dijkstra und Gries sagte mir im wesentlichen, dass, wenn ich war ein perfekter Mathematiker, ich könnte ein guter Programmierer. Der Wert hier ist, dass zu beweisen und Programmierung sind zwei etwas unterschiedliche Denkprozesse, und zumindest in meiner Erfahrung, die ich machen verschiedene Arten von Fehlern.
Meiner Erfahrung, zu beweisen-Programme ist nicht nutzlos. Wenn ich versuche etwas zu tun, was ich kann beschreiben, formal, beweist die Implementierung korrekt beseitigt eine ganze Reihe von hart-zu-finden, Fehler, die in Erster Linie verlassen, die dummen, die ich fangen kann leicht in der Testphase. An einem Projekt müssen produzieren extrem bug-free code, kann es eine sinnvolle Ergänzung. Es ist nicht geeignet für jede Anwendung, und es ist sicherlich kein Allheilmittel.
InformationsquelleAutor der Antwort
Als andere darauf hingewiesen, (einige) Programme können in der Tat nachgewiesen werden.
Einem problem in der Praxis ist jedoch, dass müssen Sie zunächst etwas (d.h. eine Annahme, die oder-theorem), dass Sie beweisen wollen. So etwas zu beweisen, über ein Programm, müssen Sie zunächst eine formale Beschreibung, was Sie tun sollen (z.B. pre - und post-Bedingungen).
In anderen Worten, müssen Sie eine formale Spezifikation des Programms. Aber immer noch eine angemessene (viel weniger eine strenge formale) Spezifikation ist schon eine der schwierigsten Dinge in der software-Entwicklung. Daher ist es im Allgemeinen sehr schwierig zu beweisen interessante Dinge über einen (real-world) Programm.
Allerdings gibt es einige Dinge, die können (und wurden) leichter formalisiert (und bewährte). Wenn kann man wenigstens beweisen, dass Ihr Programm wird nicht Abstürzen, das ist schon etwas :-).
BTW, einige compiler-Warnungen/Fehler sind im wesentlichen die (einfachen) Beweise über ein Programm. E. g., der Java-compiler wird beweisen, dass Sie nie den Zugriff auf eine nicht initialisierte variable im code (sonst wird es Ihnen zu einem compiler-Fehler).
InformationsquelleAutor der Antwort
Ich haven ' T Lesen alle Antworten, aber so wie ich das sehe, beweisen die Programme, die sinnlos ist, das ist, warum tut es niemand.
Wenn Sie einen relativ kleinen/mittleren Projekt (sagen wir, 10K Zeilen code), dann der Beweis ist wahrscheinlich gonna werden auch 10k Zeilen, wenn nicht länger.
Denken, wenn das Programm kann Fehler haben, der Nachweis kann auch "bugs". Vielleicht brauchen Sie einen Beweis für den Beweis!
Andere Sache zu prüfen, die Programme sind sehr sehr formal und präzise. Sie können nicht mehr streng und formal, weil der Programm-code ausgeführt werden soll, durch einen sehr dummen Maschine.
Während die Beweise sind, gelesen werden von Menschen, so neigen Sie dazu, weniger streng als der eigentliche code.
Nur Dinge, die Sie wollen, um zu beweisen, sind low-level-algorithmen, die auf spezielle Datenstrukturen (z.B. quicksort, insertion in einen binären Baum, etc).
Diese Dinge sind etwas komplizierter, es ist nicht sofort ersichtlich, warum Sie funktionieren und/oder ob Sie immer funktionieren. Sie sind auch die Grundbausteine für alle anderen software.
InformationsquelleAutor der Antwort
Meisten Antworten konzentriert sich auf die Praxis und das ist ok: in der Praxis kümmert man sich nicht um formale Prüfung. Aber was in der Theorie?
Programme bewiesen werden kann, genauso wie eine mathematische Aussage kann. Aber nicht in dem Sinne Sie gemeint!
In jede ausreichend leistungsstarke framework, es gibt mathematische Aussagen (und Programme), die nicht bewiesen werden kann! Sehen hier
InformationsquelleAutor der Antwort
So viel Lärm hier, aber ich werde Schreien, der wind jedenfalls...
"Als korrekt erweisen" hat verschiedene Bedeutungen in verschiedenen Kontexten. In formale Systeme"als korrekt erweisen" bedeutet, dass eine Formel abgeleitet werden kann aus anderen bewährten (oder axiomatischen) Formeln. "Als korrekt erweisen" in der Programmierung zeigt einfach, code zu sein, entspricht eine formale Spezifikation. Aber wie beweisen Sie die formale Spezifikation korrekt? Leider gibt es keine Möglichkeit zu zeigen, eine spec zu bug-frei oder eine Lösung, die jeder real-world problem anders als durch die Prüfung.
InformationsquelleAutor der Antwort
Nur meine 2 Cent hinzufügen, um die interessanten Sachen schon da.
Alle Programme, kann nicht nachgewiesen werden, die häufigsten sind diejenigen durchführen IO (einige unpredictible Interaktion mit der Welt oder dem Benutzer). Auch automatisierte Beweise manchmal nur vergessen, dass die "bewährten" Programme" laufen auf einigen physikalischen hardware, nicht das ideal, das ein beschrieben durch das Modell.
Auf der anderen Seite mathematische Beweise kümmern sich nicht viel von der Welt. Eine immer wiederkehrende Frage, mit der Mathematik ist, wenn er beschreibt, nichts wirkliches. Es wird jedes mal ausgelöst, wenn Sie etwas neues wie imaginäre zahlen oder nicht-euklidische Raum ist erfunden. Dann ist die Frage vergessen, wie diese neuen Theorien sind so gute tools. Wie ein gutes Programm, es funktioniert einfach.
InformationsquelleAutor der Antwort