Argumentation über nicht deterministisch terminierende Schleifen

10

Hier ist eine "Track B" -Frage, falls es jemals eine gab. Zusammenfassung: Das erste, woran ich denke, wenn ich versuche, nicht deterministischen Programmen eine Semantik zu geben, führt zu einer Semantik, in der ich keine Dinge über Schleifen beweisen kann, die nur nicht deterministisch enden. Sicherlich hat jemand herausgefunden, was in dieser Situation zu tun ist, oder zumindest darauf hingewiesen, dass es schwierig ist, aber ich weiß nicht, wie ich danach suchen soll (daher das Tag "Referenzanfrage").

Hintergrund

Ich möchte eine while-Sprache mit Nichtdeterminismus modellieren. Ich denke, dies ist der offensichtliche (oder zumindest naive) Weg, eine solche Sprache mit einer Smyth-Powerdomain zu modellieren, aber korrigiere mich, wenn ich falsch liege. Wir werden die Bedeutung eines Befehls in dieser Sprache als eine Funktion modellieren, deren Domäne die Menge S von Zuständen ist und deren Codomäne die Menge P(S)={}P(S) , wobei das kleinste Element ist nicht-Beendigung darstellt und P(S) ist die Powerset von Zuständen.

Wir interpretieren Befehle als Abbildungen von Zuständen σ entweder auf das oder auf Mengen von Zuständen {σ1,σ2,} die mögliche Ergebnisse darstellen. PQ ist eine nicht deterministische Wahl.

  • skipσ={σ}
  • x:=Eσ={σ[(Eσ)/x]}
  • abortσ=
  • if E then P else Qσ=Pσ if Eσ=true , andernfalls Qσ
  • PQσ= wenn Pσ= oder Qσ= , andernfalls PσQσ
  • P;Qσ= wenn oder für einige , andernfallsPσ=Qτ=τPστPσQτ

Es gibt eine gerichtete vollständige , wobei für jedes und wenn sowohl als auch richtige Mengen und , und wir können dies auf Funktionen von bis punktweise erweitern: wenn für jedes und ist die Funktion, die jeden Status .SSP(S)S1S2S1S2S1S2fSP(S)f1f2f1(σ)f2(σ)σf

Die Bedeutung einer Schleife ist ist die kleinste Obergrenze der Kette , wobei wenn , andernfalls wenn oder für einige , andernfalls . (Diese Definition geht davon aus, dass das gerade definierte Scott stetig ist, aber ich denke, es ist sicher, das beiseite zu lassen.)while E do Pσff(f)f(f(f))f(g)(σ)={σ}E(σ)=falsePσ=g(τ)=τPστPσg(τ)f

Frage

Betrachten Sie dieses Programm:

x:=0;
b:=true;
while b do
x:=x+2;
b:=falseb:=true

Intuitiv ist dies eine Schleife, die eine beliebige positive gerade Zahl zurückgeben oder nicht terminieren kann und die dem entspricht, was wir über diese Schleife unter Verwendung der schwächsten liberalen Voraussetzung beweisen können (es ist möglich zu zeigen, dass eine Schleife ist invariant). Da die Schleife jedoch nicht beendet werden kann (wir können die nicht deterministische Auswahl durch das Programm verfeinern, das immer den rechten Zweig verwendet), lautet die Bedeutung dieses Programms bei jedem Anfangszustand . (Weniger informell: Die Funktion, die jeden Zustand abbildet, in dem für sich selbst falsch ist, und jeden Zustand, in dem für wahr ist, ist ein fester Punkt des der zum Definieren der Schleife verwendet wird.)n.x=2nbbf

Dies bedeutet, dass die von mir vorgeschlagene naive Semantik nicht der Art entspricht, wie ich es mir vorstellen kann, über Programme zu argumentieren. Ich beschuldige meine Semantik, weiß aber nicht, wie ich sie reparieren soll.

Rob Simmons
quelle
4
Ich denke, dass Sie durch die Verwendung von als Codomäne für die Bedeutung eines Programms effektiv aufgegeben haben, über ein Programm nachzudenken, das divergieren kann. Ein naiver Gedanke ist, , aber ich weiß nicht, ob dies ein weiteres Problem mit sich bringt. {}P(S)P(S{})
Tsuyoshi Ito
Ja, Sie haben absolut Recht, wenn Sie sich das Set ansehen, ist es bereits offensichtlich, dass die Hoffnung verloren ist, noch bevor wir zum Beispiel kommen. Ihr Vorschlag kam mir auch in den Sinn, aber ich denke, Sie haben in diesem Beispiel das gleiche Problem, solange die potenzielle Nichtbeendigung durch not modelliert wird , und wenn Wir haben uns für Letzteres entschieden, da dies unsere Fähigkeit beeinträchtigen würde, einer Schleife als am wenigsten festen Punkt auf übliche Weise Bedeutung zu verleihen. {}P(S)S{}{}
Rob Simmons
Haben Sie sich Dynamic Logic angesehen? Die Semantik wird in Bezug auf die Beziehungen von Zuständen zu Zuständen angegeben, und Sie können die Logik verwenden, um über die teilweise und vollständige Korrektheit nachzudenken, dh über die Eigenschaften von Berechnungen, die enden, und dass alle Berechnungen mit einer bestimmten Eigenschaft enden.
Dave Clarke
Ich habe in dieser Umgebung nicht über dynamische Logik nachgedacht, aber ich sehe, wie relevant sie sein könnte - ich werde sehen, was Platzer und seine Schüler denken, wenn ich wieder in Pittsburgh bin.
Rob Simmons

Antworten:

10

In [dB80] wird nachgewiesen, dass die Analyse der Terminierungseigenschaften der Rekursion durch Hitchcock und Park einer semantischen Analyse entspricht, die auf der sogenannten Egli-Milner-Interpretation von Beziehungen basiert [Egl75, Plo76], die einen unberechenbaren Nichtdeterminismus ausdrückt . Diese Vorstellung erfasst, dass eine nichtdeterministische Vereinigung von Beziehungen korrekt ist, wenn sie mindestens eine Berechnung erzeugt, die zu einem gewünschten Ergebnis führt (selbst bei Vorhandensein einer nicht endenden Berechnung). Dies scheint dem zu entsprechen, was Sie versuchen zu tun.

Als nächstes charakterisieren Sie die Bedeutung einer Anweisung als eine Funktion die jeden Anfangszustand einem nicht leeren Satz von Zuständen , die möglicherweise , so dass in dem Sinne ist, dass . Die nichtdeterministische Wahl zwischen den Anweisungen und wird durch die Funktion beschrieben, die jeden Anfangszustand auf die Vereinigung der einzelnen Ergebnisse . Also wann immer oderSfSσfSfS()={}S1S2σfS1(σ)fS2(σ)S1S2hat die nicht deterministische Möglichkeit, ein unerwünschtes Ergebnis zu erzielen, ebenso wie ihre nicht deterministische Wahl. Als resultierende Mengen von Endzuständen erhält man in dieser Analyse das sogenannte Egli-Milner-Potenzsatz von Zuständen:

PE--M(S)={ sS | s ist endlich und nicht leer oder enthält}

Warum werden unendliche Teilmengen von in diesem Modell nicht als mögliche Mengen von Endzuständen angesehen? Unter der Annahme, dass alle Grundbausteine ​​relationaler Terme nur endliche, nicht leere Mengen möglicher Endzustände erzeugen, kann eine unendliche Menge möglicher Endzustände nur erzeugt werden, wenn eine unendliche Berechnung möglich ist. Dies kann wie folgt gesehen werden. Strukturieren Sie die Menge aller möglichen Berechnungen, die in einem bestimmten Zustand als Baum mit root und Zuständen als Knoten. Die Menge der Blätter ist dann genau die Menge der möglichen Endzustände, die von aus erreichbar , mit Ausnahme vonSσ0σ0σ0, das unter den Blättern fehlen könnte, aber in der Menge der Endzustände durch die Tatsache dargestellt wird, dass es im Baum einen unendlichen Pfad gibt. Durch die obige Annahme und da nur eine endliche nichtdeterministische Auswahl verfügbar ist, verzweigt sich dieser Baum endlich. Somit gibt es nur eine begrenzte Anzahl von Blättern in einer bestimmten endlichen Tiefe. Folglich kann eine unendliche Anzahl möglicher Endzustände nur in Gegenwart einer unendlichen Berechnung erzeugt werden (eine Anwendung von Königs Lemma [Kön32]).

(PE--M(S),E--M) ist ein Poset für definiert durch: für ,E--Ms,tPE--M(S)

sE--Mt=(ss{}t)(ss=t) .

Hier kann als Platzhalter angesehen werden, durch den größere Mengen generiert werden können, indem anstelle von weitere Zustände eingefügt werden . Daher ist das kleinste Element von . Darüber hinaus besitzt das Poset Lubs für Ketten. In ähnlicher Weise sind die strengen Funktionen von bis teilweise durch die punktweise Erweiterung von geordnet . Darüber hinaus ist die geringste solche FunktionE--M{}(PE--M(S),E--M)(PE--M(S),E--M)ωS{}PE--M(S)E--Mλσ.{} und lub's von Ketten solcher Funktionen existieren ebenfalls.ω

[dB80] JW de Bakker. Mathematische Theorie der Programmkorrektheit . Prentice Hall, 1980.

[Egl75] H Egli. Ein mathematisches Modell für nichtdeterministische Berechnungen. Technischer Bericht, ETH Zürich, 1975.

[Kön32] D König. Theorie der endlichen und unendlichen Graphen. Technischer Bericht, Leipzig, 1932.

[Plo76] GD Plotkin. Eine Powerdomain-Konstruktion. SIAM Journal on Computation , 5 (3): 452 & ndash; 487, 1976.

Haftungsausschluss: Dies stammt fast wörtlich aus einem Buch, das ich einmal mitverfasst habe:

WP de Roever und K Engelhardt. Datenverfeinerung: Modellorientierte Beweismethoden und deren Vergleich . Cambridge University Press, 1998.

Kai
quelle
4
Dem Satz "Dies ist fast wörtlich aus einem Buch entnommen, das ich einmal mitautorisiert habe" sollte wahrscheinlich "Extra Awesomeness:" vorangestellt werden, nicht "Disclaimer:" :-D. Danke, das ist sehr hilfreich.
Rob Simmons
Eine Sichtweise auf den Nichtdeterminismus (und die Art und Weise, wie ich ihn betrachten möchte) ist, dass es sich um eine Form der Unterspezifikation handelt - ein Programm mit einer nichtdeterministischen Auswahl wird durch das Programm verfeinert , das immer die erste Wahl trifft, immer die zweite Wahl trifft, oder (siehe McIver und Morgans umfangreiche Arbeit in diesem speziellen Bereich) das Programm, das mit Wahrscheinlichkeit die eine oder andere Wahl trifft .5 . Die Schleife, die nicht deterministisch nicht endet, wird also durch die Schleife verfeinert, die niemals endet, und auch durch Ihre Münzwurfschleife, die endet (mit Wahrscheinlichkeit 1)
Rob Simmons