Was wissen wir über nachweislich korrekte Programme?

37

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?

Alex ten Brink
quelle
1
Ein Compiler könnte alle möglichen Beweise der Länge i auflisten und dabei von 1 bis unendlich gehen, bis er einen Beweis findet, dass das Programm anhält. Wenn wir verlangen, dass die Eingabe für den Compiler nachweislich stoppt, findet der Compiler diesen Beweis immer. Da das Problem des Anhaltens nicht zu entscheiden ist, müssen wir schließen, dass es Programme gibt, die anhalten, aber es gibt keinen Beweis dafür. Der entscheidende Punkt ist, dass Programme nicht herausfinden können, ob ein Beweis existiert, und nicht, dass sie keinen Beweis finden können, wenn er existiert.
Alex ten Brink
3
Ich denke, Sie sollten sie aufteilen. Es sind unterschiedliche Fragen mit unterschiedlichen Antworten.
Mark Reitblatt
4
Ein einflussreiches Papier zur ersten Frage ist "Soziale Prozesse und Beweise für Theoreme und Programme", portal.acm.org/citation.cfm?id=359106
Colin McQuillan,
1
Die Programmüberprüfung ist unentscheidbar. Ein Problem ist also zu sagen, was eine gute Lösung darstellt. Siehe cstheory.stackexchange.com/questions/4016/…
Radu GRIGore
2
@Colin: Dieses Papier ist für seine Beweisanalyse lesenswert, aber seine Vorhersagen wurden gefälscht. Heute haben wir nachweislich korrekte Compiler, Betriebssystemkerne, Garbage Collectors und Datenbanken, die alle als unmöglich vorausgesagt wurden. Der Trick, sich ihrer Kritik zu entziehen, bestand darin, die Überprüfung der Details formaler Beweise durch den Menschen zu vermeiden, die maschinelle Überprüfung von Beweisen zu verwenden und den Menschen zur Überprüfung des Proof-Checkers zu verwenden. Noams Referenz zur Typentheorie ist der Stand der Technik, der imperative Programme in gewisser Weise bindet, da die Typentheorie funktional ist.
Neel Krishnaswami

Antworten:

28

"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.kkk

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.

Neel Krishnaswami
quelle
1
Könnten Sie diesen Punkt "Wir werden nur Programme mit verwaltbaren Termination Proofs schreiben" etwas ausführlicher erläutern?
Dai Le
Danke für deine aktualisierte Antwort! Ihre Antwort öffnet wirklich meine Perspektive. Eigentlich beschäftige ich mich auch ein bisschen mit "umgekehrter Mathematik", aber ich habe den von Ihnen erwähnten Zusammenhang nicht erkannt. Danke noch einmal!
Dai Le
1
Der Punkt in Ihrer Bearbeitung hängt damit zusammen, dass wir kaum Kandidaten für Tautologien haben, die lange Beweise in natürlichen Beweissystemen erfordern (wie zum Beispiel Frege). Ein Grund dafür ist, dass wir eine Tautologie nur dann kennen, wenn wir einen Beweis im Sinn hatten, der notwendigerweise nicht so lange dauerte!
Joshua Grochow
22

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.


AC0AC0-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ϵ0TPA2FIΣ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.


PnnPAlgorithmus 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.)

Kaveh
quelle
3
Gute Antwort! Sie erwähnen, dass eine Möglichkeit darin besteht, Programme aus Proofs zu extrahieren, was beispielsweise in Coq automatisch möglich ist. Ein verwandter Bereich ist das Proof-Mining , bei dem Personen (die normalerweise in mathematischer Logik arbeiten) versuchen, Informationen aus einem bestimmten Beweis zu extrahieren. Zum Beispiel ist es in einigen Fällen möglich, (automatisch) einen intuitionistischen Beweis für einen klassischen zu finden.
Radu GRIGore
1
Π20PAHA
1
Andrej Bauer hat einen neuen interessanten Beitrag in seinem Blog, in dem er Godels Dialectica Interpretation in Coq .
Kaveh
18

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.

Noam Zeilberger
quelle
8
Ich würde sagen, dass beim Erstellen verifizierter Software 1956 einfache alte Software erstellt wurde. Es war bereits klar, dass Software unglaublich wichtig sein würde, und es gab bereits wichtige Erfolgsgeschichten. Es fehlten jedoch noch viele grundlegende Konzepte (zum Beispiel ein klares Verständnis der Prozeduren und Variablen), und die Entfernung von der Theorie zur Praxis könnte so kurz sein wie die Implementierung von Lisp durch Programmieren des Codes in einem Theorem. Dies ist eine UNGLAUBLICH aufregende Zeit, um an Sprachen und Verifikationen zu arbeiten.
Neel Krishnaswami
12

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 .

Radu GRIGore
quelle
Soweit ich Spec # (und seine Erweiterung Sing #) verstehe, kann der Programmierer Asserts statisch verifizieren, ohne dass dies vom Programmierer verlangt wird, und es wird auch nicht die Möglichkeit geboten, beliebige Eigenschaften des Codes zu beweisen.
Alex ten Brink
Beliebige Eigenschaften können grundsätzlich als fol gende Aussagen kodiert werden. Ich bin mir nicht sicher, was Sie für das Tool benötigen. Soll in den Spezifikationen angegeben werden, wie die Ausgabe für alle möglichen Eingaben lauten soll?
Radu GRIGore
4

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/TMNonemptiness/TMEmptiness/TMEmptiness/TMEquivalence/TMEquivalence/TMist 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.

TrueRTrueRR

ProvableR=TrueRProvableRTrueRTrueRProvableRAϵTrueRAAAϵ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.

RProvableRProvableRRR

@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.

Chazisop
quelle
1
RProvableRΣ30Σ10
1
Beweisbar bedeutet immer, in einem System / einer Theorie beweisbar zu sein und stimmt im Allgemeinen nicht mit der Wahrheit überein.
Kaveh
1
Ich verstehe jetzt, dass man, um meine Frage interessant zu machen, über das Anhalten der Turing-Maschinen sprechen sollte, nicht über die entscheidbaren Sprachen.
Alex ten Brink
1
@Alex Nun, du brauchst eine Art über Sprachen zu sprechen, aber es gibt unzählige. Wenn Sie also über Sprachen sprechen möchten, die mit einem endlichen Objekt verbunden sind (wie ein Beweis), müssen Sie sich auf Sprachen beschränken, die durch ein endliches Objekt, wie ein TM, identifizierbar sind.
Mark Reitblatt
2
R
3

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(Mi)|Ti(n)T(n) is provable in F}MiTi(n)Min

T(n)nlog(n)g(n)1FTIME[T(n)]TIME[T(n)g(n)]

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

Satz 6.14: Für jedes berechenbare ist .T(n)nlog(n)TIME[T(n)]={L(Mi)|F proves(j)[L(Mj)=L(Mi)Tj(n)T(n)]}

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

Satz 6.9: (1) Wenn ist, dann ist - .s(n)nSPACE[s(n)]=FSPACE[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)]=FSPACE[S(n)]S(n)ns(n)SPACE[S(n)]=SPACE[s(n)]

Joshua Grochow
quelle
1

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.

Victor Yodaiken
quelle