Was wissen wir über nachweislich korrekte Programme?

Die ständig zunehmende Komplexität von Computerprogrammen und die immer wichtigere Position von Computern in unserer Gesellschaft lassen mich fragen, warum wir immer noch keine Programmiersprachen gemeinsam verwenden, in denen Sie einen formalen Nachweis erbringen müssen, dass Ihr Code ordnungsgemäß funktioniert.

Ich glaube, der Begriff ist ein "zertifizierender Compiler" (ich habe ihn hier gefunden ): ein Compiler, der eine Programmiersprache kompiliert, in der man nicht nur den Code schreiben, sondern auch die Spezifikation des Codes angeben und nachweisen muss, dass der Code dem entspricht Spezifikation (oder verwenden Sie einen automatisierten Beweiser, um dies zu tun).

Bei der Suche im Internet habe ich nur Projekte gefunden, die entweder eine sehr einfache Programmiersprache verwenden, oder gescheiterte Projekte, die versuchen, moderne Programmiersprachen anzupassen. Dies führt mich zu meiner Frage:

Gibt es zertifizierende Compiler, die eine vollständige Programmiersprache implementieren, oder ist dies sehr schwierig / theoretisch unmöglich?

Außerdem habe ich noch keine Komplexitätsklasse mit beweisbaren Programmen gesehen, wie zum Beispiel "die Klasse aller Sprachen, die von einer Turing-Maschine entschieden werden können, für die ein Beweis dafür vorliegt, dass diese Turing-Maschine anhält", die ich $ProvableR$ ist analog zu $R$ die Menge der rekursiven Sprachen.

Ich kann Vorteile sehen , eine solche Komplexitätsklasse Studium: zum Beispiel für $ProvableR$ das Halteproblem entscheidbar ist (ich selbst Vermutung $ProvableRE$ in der offensichtlichen Weise definiert wäre die größte Klasse von Sprachen, für die entschieden werden kann). Außerdem bezweifle ich, dass wir praktisch nützliche Programme ausschließen würden: Wer würde ein Programm verwenden, wenn Sie nicht nachweisen können, dass es beendet ist?

Meine zweite Frage lautet also:

Was wissen wir über Komplexitätsklassen, bei denen die enthaltenen Sprachen nachweislich bestimmte Eigenschaften haben müssen?

"Compiler zertifizieren" bedeutet normalerweise etwas anderes: Es bedeutet, dass Sie einen Compiler haben, der nachweisen kann, dass der von ihm ausgegebene Maschinencode die allgemeine Semantik korrekt implementiert. Das heißt, dies ist ein Beweis dafür, dass es keine Compiler-Fehler gibt. Die Programme, die der Compiler erhält, können immer noch falsch sein, der Compiler generiert jedoch eine korrekte Maschinencodeversion des falschen Programms. Die größte Erfolgsgeschichte in dieser Hinsicht ist der CompCert-verifizierte Compiler , der einen Compiler für eine große Teilmenge von C darstellt.

Der Compcert-Compiler selbst ist ein Programm mit einem Korrektheitsnachweis (in Coq erstellt), der garantiert, dass, wenn Code für ein Programm generiert wird, dieser korrekt ist (in Bezug auf die von den CompCert-Designern verwendete Betriebssemantik von Assembly & C). Der Aufwand, diese Dinge maschinell zu überprüfen, ist ziemlich groß; Normalerweise liegt der Korrektheitsnachweis zwischen 1x und 100x der Größe des zu überprüfenden Programms. Das Schreiben von maschinengeprüften Programmen und Beweisen ist eine neue Fähigkeit, die Sie lernen müssen - es ist nicht wie üblich Mathematik oder Programmierung, obwohl es von der Fähigkeit abhängt, beides gut zu können. Es fühlt sich an, als würden Sie von vorne anfangen, als wären Sie wieder ein Anfänger in der Programmierung.

Hierfür gibt es jedoch keine besonderen theoretischen Hindernisse. Das einzige, was in diese Richtung geht, ist das Blum-Size-Theorem , das besagt, dass Sie für jede Sprache, in der alle Programme total sind, ein Programm in einer allgemein rekursiven Sprache finden können, das mindestens exponentiell größer ist, wenn es in der Gesamtsprache programmiert wird. Der Weg, dieses Ergebnis zu verstehen, besteht darin, dass eine Gesamtsprache nicht nur ein Programm, sondern auch einen Terminierungsnachweis codiert. So können Sie kurze Programme mit langen Abschlussprüfungen haben. In der Praxis spielt dies jedoch keine Rolle, da wir nur Programme mit verwaltbaren Termination Proofs schreiben werden.

EDIT: Dai Le bat um eine Ausarbeitung des letzten Punktes.

Dies ist meistens eine pragmatische Behauptung, die auf der Tatsache beruht, dass, wenn Sie verstehen können, warum ein Programm funktioniert, es unwahrscheinlich ist, dass der Grund eine riesige Invariante ist, die Millionen von Seiten umfasst. (Die längsten Invarianten, die ich verwendet habe, sind ein paar Seiten lang, und sie bringen die Rezensenten zum Murren. Verständlicherweise auch, da die Invariante der Grund ist, warum das Programm ohne die gesamte Erzählung arbeitet, die den Leuten hilft, es zu verstehen.)

Aber es gibt auch einige theoretische Gründe. Grundsätzlich kennen wir nicht viele Möglichkeiten, Programme systematisch zu erfinden, deren Korrektheitsnachweise sehr lang sind. Die Hauptmethode besteht darin, (1) die Logik zu verwenden, in der Sie die Richtigkeit nachweisen, (2) eine Eigenschaft zu finden, die in dieser Logik nicht direkt ausgedrückt werden kann (Konsistenznachweise sind die typische Quelle), und (3) ein Programm zu finden, dessen Der Korrektheitsnachweis beruht auf einer Reihe von ausdrücklichen Konsequenzen des unaussprechlichen Eigentums. Da (2) unaussprechlich ist, bedeutet dies, dass der Beweis für jede ausdrückliche Konsequenz unabhängig durchgeführt werden muss, wodurch Sie die Größe des Korrektheitsbeweises sprengen können. Beachten Sie als einfaches Beispiel, dass Sie in der Logik erster Ordnung mit einer übergeordneten Beziehung die Vorfahrenbeziehung nicht ausdrücken können.$k$$k$$k$

Die differenzierte Sichtweise auf dieses Thema wird "Umkehrmathematik" genannt und ist das Studium der Axiome, die erforderlich sind, um gegebene Theoreme zu beweisen. Ich weiß nicht so viel darüber, aber wenn Sie eine Frage zu ihrer Bewerbung an CS stellen und ich bin sicher, dass Timothy Chow und wahrscheinlich mehrere andere Leute Ihnen interessante Dinge erzählen können.

Ich denke die Antwort auf die erste Frage ist, dass es im Allgemeinen zu viel Arbeit mit aktuellen Tools ist. Um das Gefühl zu bekommen, schlage ich vor, die Korrektheit von Bubble Sort in Coq zu beweisen (oder wenn Sie eine etwas größere Herausforderung bevorzugen, verwenden Sie Quick Sort). Ich halte es nicht für vernünftig, von Programmierern zu erwarten, dass sie verifizierte Programme schreiben, solange es so schwierig und zeitaufwendig ist, die Korrektheit derartiger grundlegender Algorithmen zu beweisen.

Diese Frage ist vergleichbar mit der Frage, warum Mathematiker keine formalen Beweise schreiben, die von Beweisprüfern überprüft werden können. Wenn Sie ein Programm mit einem formalen Korrektheitsnachweis schreiben, müssen Sie einen mathematischen Satz über den geschriebenen Code beweisen. Die Antwort auf diese Frage gilt auch für Ihre Frage.

Dies bedeutet nicht, dass es keine erfolgreichen Fälle von verifizierten Programmen gegeben hat. Ich weiß, dass es Gruppen gibt, die die Korrektheit von Systemen wie dem Hypervisor von Microsoft beweisen . Ein verwandter Fall ist der Verified C Compiler von Microsoft . Im Allgemeinen müssen die aktuellen Tools jedoch stark weiterentwickelt werden (einschließlich ihrer SE- und HCI-Aspekte), bevor sie für allgemeine Programmierer (und Mathematiker) von Nutzen sind.

In Bezug auf den letzten Absatz von Neels Antwort zum Programmgrößenwachstum für Sprachen mit nur Gesamtfunktionen ist es eigentlich einfach, noch mehr zu beweisen (wenn ich es richtig verstanden habe). Es ist zu erwarten, dass die Syntax einer Programmiersprache ce ist und die Menge der gesamt berechenbaren Funktionen nicht ce ist. Für jede Programmiersprache, in der alle Programme gesamt sind, gibt es also eine gesamt berechenbare Funktion, die von keinem Programm berechnet werden kann ( jeder Größe) in dieser Sprache.

$AC^0$$AC^0$-komplett für die Komplexitätsklasse, enthält daher alle Probleme in der Komplexitätsklasse und kann die Gesamtheit dieser Programme beweisen. Die Beziehung zwischen Beweisen und Komplexitätstheorie wird in Bezug auf die Beweiskomplexität untersucht, siehe das kürzlich erschienene Buch " Logical Foundations of Proof Complexity " von SA Cook und P. Nguyen, wenn Sie interessiert sind. (Ein Entwurf von 2008 liegt vor.) Die grundlegende Antwort lautet also, dass für viele Klassen "Nachweislich C = C" gilt.

$PA$$\epsilon_0$$T$$PA^2$$F$$I\Sigma_1$

Es scheint mir jedoch nicht, dass dies im Kontext der Programmüberprüfung viel bedeutet, da es auch Programme gibt, die dieselbe Funktion ausführlich berechnen, aber wir können nicht beweisen, dass die beiden Programme dieselbe Funktion berechnen, dh die Programme sind ausführlich gleich, aber nicht absichtlich. (Dies ist dem Morgenstern und dem Abendstern ähnlich.) Außerdem ist es einfach, ein gegebenes nachweislich gesamtes Programm zu modifizieren, um eines zu erhalten, dessen Gesamtheit die Theorie nicht beweisen kann.

$P$$n$$n$$P$Algorithmus zur Faktorisierung aus dem Beweis. (Es gibt auch Forscher, die versuchen, den ersten Ansatz so weit wie möglich zu automatisieren, aber die Überprüfung interessanter, nicht trivialer Eigenschaften von Programmen ist rechnerisch schwierig und kann ohne falsch positive und negative Ergebnisse nicht vollständig verifiziert werden.)

Was Sie in der ersten Frage fragen, wird manchmal als "Überprüfungs-Compiler" bezeichnet, und vor einigen Jahren bot Tony Hoare dies als große Herausforderung für die Computerforschung an . Bis zu einem gewissen Grad existiert dies bereits und ist im aktiven Einsatz in Werkzeugen wie der Coq Theorembeweisers , das das Problem mit Hilfe organisiert Typentheorie und die Sätze-as-Typen - Prinzip ( „ Curry-Howard “).

BEARBEITEN: wollte nur die Betonung auf "bis zu einem gewissen Grad". Dies ist alles andere als ein gelöstes Problem, aber der Erfolg von Coq lässt hoffen, dass es kein Wunschtraum ist.

Ein Tool, das überprüft, ob ein Programm korrekt ist, wird manchmal als Programmverifizierer bezeichnet. In diesem Zusammenhang bedeutet "korrekt" normalerweise zwei Dinge: dass das Programm niemals bestimmte Ausgaben erzeugt (etwa Segmentierungsfehler, NullPointerException usw.) und dass das Programm einer Spezifikation zustimmt.

Der Code und die Spezifikation stimmen möglicherweise überein und werden dennoch als falsch empfunden. In gewissem Sinne bedeutet das Auffordern von Entwicklern, Spezifikationen zu schreiben, dass zwei Entwickler gebeten werden, das Problem zu lösen. Wenn die beiden Implementierungen übereinstimmen, haben Sie ein höheres Vertrauen, dass sie in Ordnung sind. In einem anderen Sinne sind Spezifikationen jedoch besser als eine zweite Implementierung. Da die Spezifikation nicht effizient oder sogar ausführbar sein muss, kann sie sehr viel prägnanter und daher schwieriger zu verwechseln sein.

In Anbetracht dieser Einschränkungen empfehle ich Ihnen, sich den Spec # -Programmprüfer anzusehen .

Im allgemeinen Fall ist es unmöglich, einen Algorithmus zu erstellen, der bestätigt, ob ein Algorithmus einer Spezifikation entspricht. Dies ist ein informeller Beweis:

Fast alle Programmiersprachen sind Turing-komplett. Daher kann jede von einem TM bestimmte Sprache auch von einem in dieser Sprache geschriebenen Programm bestimmt werden.

$Equivalence/TM$

$Equivalence/TM$$Non-emptiness/TM$$Emptiness/TM$$Emptiness/TM$$Equivalence/TM$$Equivalence/TM$ist auch inakzeptabel. Aus diesem Grund können Sie einen Algorithmus verwenden, unabhängig davon, ob zwei Maschinen nicht gleichwertig sind, aber Sie können nicht sicher sein, ob sie gleichwertig sind, oder Sie haben Ihrem Algorithmus nicht genügend Zeit eingeräumt.

Dies gilt jedoch nur für den allgemeinen Fall. Es ist möglich, dass Sie entscheiden können, ob die Spezifikationen dem Programm entsprechen oder nicht, indem Sie eine entspanntere Version des Problems lösen. Sie können beispielsweise nur eine Reihe von Eingaben untersuchen oder sagen, dass die beiden Programme mit einer gewissen Unsicherheit gleichwertig sind. Darum geht es beim Testen von Software.

Wie für den Rest Ihrer Fragen:

Hinweis: Dieser Teil wurde zur Verdeutlichung bearbeitet. Es stellt sich heraus, dass ich den Fehler gemacht habe, den ich zu vermeiden versuchte, sorry.

$TrueR$$TrueR \subseteq R$

$ProvableR = TrueR$$ProvableR \subset TrueR$$TrueR \subset ProvableR$$A \epsilon TrueR$$A$$A$$A \epsilon ProvableR$

Informell kann dies wie folgt zusammengefasst werden: Sie wissen nicht, dass eine Sprache entscheidbar ist, bis Sie bewiesen haben, dass es sich um eine Sprache handelt. Wenn Sie also in einem formalen System das Wissen haben, dass eine Sprache entscheidbar ist, kann dieses Wissen auch als Beweis dafür dienen. Daher können Sie nicht gleichzeitig das Wissen haben, dass eine Sprache sowohl entscheidbar ist als auch bewiesen werden kann, sodass sich diese beiden Aussagen gegenseitig ausschließen.

$R$$ProvableR$$ProvableR \subset R$$R$

@Kaveh fasst es am besten zusammen: Beweisbar bedeutet immer nachweisbar in einem System / einer Theorie und stimmt nicht mit der Wahrheit im Allgemeinen überein.

Dasselbe gilt für jede andere Komplexitätsklasse: Um die Mitgliedschaft zu bestimmen, benötigen Sie zuerst einen Beweis. Aus diesem Grund glaube ich, dass Ihre zweite Frage zu allgemein ist, da sie nicht nur Komplexitätstheorie, sondern auch Berechnungstheorie enthält, abhängig von der Eigenschaft, die die Sprache haben soll.

Die folgende klassische Monographie untersucht fast genau Ihre zweite Frage:

Hartmanis, J. Machbare Berechnungen und nachweisbare Komplexitätseigenschaften , CBMS-NSF-Regionalkonferenzreihe für Angewandte Mathematik, 30. Gesellschaft für industrielle und angewandte Mathematik (SIAM), Philadelphia, PA, 1978.

$\{L(M_i) | T_i(n) \leq T(n) \text{ is provable in F}\}$$M_i$$T_i(n)$$M_i$$n$

$T(n) \geq n \log(n)$$g(n) \geq 1$$F$$TIME[T(n)] \subsetneq TIME[T(n) g(n)]$

Satz 6.5: Es gibt berechenbare monoton ansteigende Zeitgrenzen für die - .$T(n)$$F$$TIME[T(n)] \neq TIME[T(n)]$

Satz 6.14: Für jedes berechenbare ist .$T(n) \geq n \log(n)$$TIME[T(n)] = \{ L(M_i) | \text{F proves} (\exists j)[L(M_j) = L(M_i) \wedge T_j(n) \leq T(n)] \}$

Für den Weltraum ist die Situation jedoch besser beherrschbar:

Satz 6.9: (1) Wenn ist, dann ist - .$s(n) \geq n$$SPACE[s(n)] = F$$SPACE[s(n)]$

(2) Wenn - ( ), dann gibt es ein raumkonstruierbares so dass .S P A C E [ S ( n ) ] S ( n ) ≥ n s ( n ) S P A C E [ S ( n ) ] = S P A C E [ s ( n ) $SPACE[S(n)]=F$$SPACE[S(n)]$$S(n) \geq n$$s(n)$$SPACE[S(n)]=SPACE[s(n)]$

Die Frage muss richtig gestellt werden. Zum Beispiel möchte niemand jemals wissen, ob ein tatsächliches Programm bei gegebenem unendlichen Speicher und einigen Zugriffsmöglichkeiten vollständig ist (möglicherweise eine Operation zum Verschieben der Basisadresse um eine bestimmte Nummer). Turings Satz ist für die Programmkorrektheit im konkreten Sinne irrelevant, und Leute, die ihn als Hindernis für die Programmverifikation anführen, verwechseln zwei ganz verschiedene Dinge. Wenn Ingenieure / Programmierer von Programmkorrektheit sprechen, wollen sie etwas über endliche Eigenschaften wissen. Dies gilt auch für Mathematiker, die sich dafür interessieren, ob etwas beweisbar ist. Godels Brief http://vyodaiken.com/2009/08/28/godels-lost-letter/ erklärt dies ausführlich.

Es würde nämlich offensichtlich bedeuten, dass trotz der Unentscheidbarkeit des Entscheidungsproblems die mentale Arbeit eines Mathematikers in Bezug auf Ja-oder-Nein-Fragen vollständig durch eine Maschine ersetzt werden könnte. Schließlich müsste man einfach die natürliche Zahl n so groß wählen, dass es keinen Sinn macht, mehr über das Problem nachzudenken, wenn die Maschine kein Ergebnis liefert.

Es kann durchaus unmöglich sein, den immensen Status eines auf einem Computer ausgeführten Programms zu untersuchen und fehlerhafte Status zu ermitteln. Es gibt keinen theoretischen Grund, warum dies nicht möglich ist. Tatsächlich hat es in diesem Bereich große Fortschritte gegeben - siehe zum Beispiel http://www.cs.cornell.edu/gomes/papers/SATSolvers-KR-book-draft-07.pdf (Dank an Neil Immerman für erzähl mir davon)

Ein anderes und schwierigeres Problem besteht darin, genau anzugeben, welche Eigenschaften ein Programm haben soll, um korrekt zu sein.