Was macht eine Sprache (und ihr Typensystem) in der Lage, Theoreme über ihre eigenen Begriffe zu beweisen?

12

Ich habe kürzlich versucht, Aarons Cedille-Core zu implementieren , eine minimalistische Programmiersprache, die mathematische Theoreme zu ihren eigenen Begriffen beweisen kann. Ich habe auch eine Induktion für λ-codierte Datentypen darauf nachgewiesen, was klarer machte, warum seine Erweiterungen notwendig wären.

Trotzdem frage ich mich immer noch, woher diese Erweiterungen stammen. Warum sind sie was sie sind? Was rechtfertigt sie? Ich weiß zum Beispiel, dass einige Erweiterungen wie die Rekursion die Sprache als Beweissystem ruinieren. Wenn ich mich entschließen würde, CoC auch mit anderen Primitiven zu erweitern, wie würde ich das rechtfertigen? Ich verstehe, dass ein Beweis der Normalisierung notwendig ist, aber das beweist nicht, dass diese Primitive "Sinn machen".

Kurz gesagt, was genau qualifiziert eine Sprache (und ihr Typensystem) als ein System, das Theoreme über ihre eigenen Begriffe beweisen kann?

type-theory functional-programming constructive-mathematics MaiaVictor
quelle
Ich habe einen Blog gelesen, der sich auf diese Frage bezog, aber ich kann ihn jetzt nicht finden :( Er enthielt den Satz "System T ist genug!" Oder ähnliches und sprach über abhängige Typsysteme.
Labbekak
2
Gefunden: queuea9.wordpress.com/2010/01/17/… Es wurde tatsächlich von Aaron Stump geschrieben, sodass Sie vielleicht bereits darüber Bescheid wissen.
Labbekak
Unbewachte Rekursion "ruiniert" die Sprache als Beweissystem, bewachte Rekursion nicht. Um zu beweisen, dass die Grundelemente sinnvoll sind, würde ich sagen, dass Sie ein Modell erstellen. Und um Theoreme über ihre eigenen Begriffe zu beweisen, braucht es eine Art Curry-Howard-Isomorphismus und einen abhängigen Typ, damit die Dinge, die Sie beweisen (Typen), über Ihre Begriffe sprechen können.
Xavierm02

Antworten:

5

[Selbstwerbung folgt, aber ich denke, dass dies relevant ist.]

tut≡utu∀v,(λx.x)v≡v

Natürlich können Sie auch Äquivalenzen annehmen, und es gibt verschiedene Arten von Quantifizierern (typisiert / untypisiert, universell / existentiell). Dieser Mechanismus kann verwendet werden, um über ein Programm nachzudenken (es muss nicht bewiesen werden, dass es beendet oder sogar getippt wurde). Die einzige Einschränkung besteht darin, dass Programme, die als Beweise verwendet werden, vom System als terminierend nachgewiesen werden müssen (willkürliche allgemeine Rekursion führt zu Inkonsistenz).

Hier sind ein paar Referenzen, wenn Sie dies überprüfen möchten:

Rodolphe Lepigre
quelle