Was ist ein Beispiel für eine konstruktive oder eine nichtkonstruktive Typentheorie?
Ich versuche, einige grundlegende Begriffe in Bezug auf die Typentheorie zu verstehen, und verstehe derzeit den Unterschied zwischen "konstruktiven Typentheorien" und "nichtkonstruktiven Typentheorien", wie hier erwähnt :
Wie die Logik erster Ordnung ist auch die Typentheorie der Kirche klassisch in dem Sinne, dass sie nichtkonstruktive Argumentationsprinzipien wie das Gesetz der ausgeschlossenen Eliminierung der mittleren und doppelten Negation zulässt . P. Martin-Löf führte 1972 eine konstruktive Form der Typentheorie ein, die heute als Martin-Löf-Typentheorie bekannt ist [42]. Die meisten konstruktiven Typentheorien, einschließlich der Martin-Löf-Typentheorie, verkörpern den Curry-Howard-Isomorphismus [33], der Beweissätze in der Typentheorie elegant mit dem Schreiben von Programmen in der Lambda-Rechnung verbindet. Konstruktive Typentheorien haben auch eine enge Verbindung zur Kategorietheorie und wurden ausgiebig verwendet, um konstruktive Mathematik und Ideen aus der theoretischen Informatik zu formalisieren [12, 39].
Das Beispiel von Wikipedia für konstruktive und nicht konstruktive Beweise hilft nicht, die Konzepte zu erläutern. Ich bin mir nicht ganz sicher, ob dies mit dem Konstruktivismus in der Mathematik zu tun hat , aber es scheint so.
Was genau gemeint konstruktiv gegenüber relativ schlechten hinsichtlich der Typentheorie? Was ist ein Beispiel, um den Unterschied zwischen konstruktiven und nichtkonstruktiven Typentheorien zu demonstrieren? Wie würde ich einem Nichtmathematiker wie einem Softwareentwickler den Unterschied zwischen konstruktiven und nichtkonstruktiven Typentheorien erklären?
Antworten
Wie im zitierten Text erwähnt, hat der Unterschied zwischen konstruktiver und nichtkonstruktiver Typentheorie mit dem Konstruktivismus in der Mathematik zu tun. Da es viele Variationen der konstruktiven Mathematik gibt , ist es einfach unmöglich, den Unterschied zwischen konstruktiver und nicht konstruktiver genau zu definieren.
Konstruktivität hat aber auch eine technische Bedeutung in der Typentheorie. Eine Typentheorie ist konstruktiv, wenn sie die Kanonizitätseigenschaft besitzt : Jeder Term eines bestimmten Typs berechnet sich zu einer kanonischen Form , dh einer Kombination der einzigen Konstruktoren dieses Typs.
Mit nichtkonstruktiven Axiomen wie der ausgeschlossenen Mitte können Sie die Existenz eines Begriffs eines bestimmten Typs nachweisen, aber Sie können diesen Begriff nicht berechnen (in kanonischer Form).