Welche Funktionen kann System F nicht berechnen?

28

In diesem Wikipedia-Artikel zu Turing Completeness heißt es:

Der untypisierte Lambda-Kalkül ist vollständig, viele typisierte Lambda-Kalküle, einschließlich System F, jedoch nicht. Der Wert typisierter Systeme beruht auf ihrer Fähigkeit, die meisten typischen Computerprogramme darzustellen und gleichzeitig mehr Fehler zu erkennen.

Was ist ein Beispiel für eine vollständig berechenbare Funktion, die von System F nicht berechenbar ist ?

Da hindley-milner außerdem ist:

Eine Einschränkung von System F

aufgrund der Tatsache, dass:

Die Typprüfung ist für eine Curry-artige Variante von System F unentscheidbar, dh für eine Variante, der explizite Typanmerkungen fehlen.

Bedeutet dies, dass der Lambda-Kalkül, der den Systemen vom Hindley-Milner-Typ zugrunde liegt, nicht vollständig ist?

Wenn dies zutrifft, werden die Merkmale, die in der Lambda-Rechnung nicht vorhanden sind, hinzugefügt, um die Hashkell-Rechnung zu vervollständigen , da die Hashkell-Rechnung eindeutig vollständig ist und wir wissen, dass sie auf der Lambda-Rechnung und dem Hindley-Milner-System basiert.

Mike HR
quelle
Ein Beispiel für eine Funktion, die Haskell komplett macht, ist die native Codeschnittstelle.
Trismegistos
@cody danke für deinen Kommentar. Ich bin mit System T nicht vertraut. Habe ich Recht, wenn ich davon ausgehe, dass es sich um das hier erwähnte System T handelt ? Wie vergleicht und kontrastiert System T mit System F?
Mike HR
HINWEIS auf googeln für system T vs. system Ffand ich etwas , das meine letzte Teilfrage beantwortet , die wie hier neu formuliert wird: Wie Haskell Turing-Vollständigkeit zu System F hat hinzufügen
Mike HR
1
Ich denke, @Trismegistos wirft eine interessante philosophische Frage auf: Was genau ist Haskell, wo liegen seine Grenzen?
Martin Berger

Antworten:

45

System ist sehr ausdrucksstark. Wie hier von Girard bewiesen , sind die Funktionen vom Typ (wobei definiert ist als ) sind genau die definierbaren Funktionen ( ) in Heyting Arithmetic zweiter Ordnung . Beachten Sie, dass dies mit den Funktionen identisch ist, die in der Peano-Arithmetik zweiter Ordnung definiert werden können .FNNNX. X(XX)XNNHA2

Wahrscheinlich möchten Sie Proofs und Typen als besser lesbare Referenz überprüfen . Beachten Sie, dass dies bedeutet , dass eine Menge von Programmen kann in System F geschrieben wird, von der Ackermann - Funktion Dolmetscher für Gödels System . Wie für jede Programmiersprache (mit einigen milden Bedingungen) kann System keinen Selbstinterpreter implementieren , dh eine Funktion die als Eingabe einen Code für einen Term verwendet von System und gibt eine (Code für a) normale Form fürTFeval:NNtFt. Der Beweis beinhaltet eine Variante des Diagonalisierungstricks, der für die Unentscheidbarkeit des Halteproblems verwendet wird. Andrej erklärt es hier wunderschön .

Um Ihre anderen Fragen zu beantworten: Die -calculus zugrunde liegenden Hindley-Milner (HM) -Sprachen sind ebenfalls nicht vollständig. Tatsächlich ist es signifikant schwächer als System weist eine geringere Aussagekraft auf als der einfach typisierte Kalkulus.λF λ

Haskell ist in der Tat Turing vollständig. Das auffälligste Merkmal, das dies ermöglicht (obwohl es andere gibt), ist das Vorhandensein einer uneingeschränkten Rekursion : Die Definition eines Programms (einer Funktion) kann sich auf das Programm selbst beziehen. Dies ist vergleichbar mit der Hinzufügung eines Kombinators, wie er in der Definition von PCF vorgenommen wird, der einfach eingegeben wird, aber die Turing-Vollständigkeit des Kombinators beibehält .YY

Beachten Sie, dass es andere Funktionen gibt, die Haskell Turing vervollständigen, die jedoch normalerweise nicht als Teil der Kernsprache betrachtet werden, z. B. Verweise auf Funktionen, uneingeschränkte Datentypen usw.

Cody
quelle
1
Wow, das ist eine erstaunliche Antwort und beantwortet alles perfekt. Vielen Dank!
Mike HR
"Wie für jede Programmiersprache ..." Dies ist nicht ganz richtig. Es gibt einige Selbstinterpretierer für Gesamtsprachen, die funktionieren, indem nach meinem Verständnis nicht terminierende Programme als falsch geschrieben ausgeschlossen werden. Siehe dieses Papier
jmite
@jmite wie gesagt, mein anspruch ist korrekt. Dieses Papier wird in der verlinkten Diskussion erwähnt, und Andrej hat einige nachfolgende Bemerkungen in seinem Blog: math.andrej.com/2016/01/04/…
cody
11

Es ist etwas irreführend zu sagen, dass Haskells Typisierungssystem "das Hinley-Milner-Typisierungssystem" ist. Haskells Typen sind viel leistungsfähiger, darunter auch Typen höherer Klassen. Tatsächlich ist das Schreibsystem so leistungsfähig, dass Sie Turing-vollständige Programmiersprachen in das Schreibsystem einbetten können, siehe hier . Dies ist nicht der einzige Grund für Haskells Macht, Cody hat einige andere erwähnt.

Martin Berger
quelle
Vielen Dank. Mein Hauptkontakt mit Hindley-Milner war durch Haskell. Ich glaube, ich habe angenommen, dass höherwertige Typen ein Teil davon waren. Bezieht sich Hindley-Milner nur auf die Typinferenz (also höchstwahrscheinlich auf den Algorithmus W)? oder ist es etwas mehr Ich verstehe, dass es die mathematische Grundlage dafür in der Lambda-Rechnung gibt. Ich versuche nur zu verstehen, wo die logischen Grenzen zwischen dem leistungsfähigen Typensystem von haskell und einer minimalen Implementierung eines "Hindley-Milner-Typensystems" liegen.
Mike HR
NB Wenn jemand an der Leistungsfähigkeit des Haskell-Typ-Systems interessiert ist, würde ich Edward Kmetts Video über Hask empfehlen , das (tief) in die Kategorietheorie mit dem Haskell-Typ-System eintaucht.
Mike HR
1
@ MikeH-R Normalerweise meinen wir, dass Hindley-Milner ein Typisierungssystem oder genauer gesagt ein typisierter Kalkül ist, während der Algorithmus ein Typisierungsalgorithmus für das Hindley-Milner-System ist. Das Besondere am Hindley-Milner-System ist, dass es parametrischen Polymorphismus mit der Fähigkeit kombiniert, den allgemeinsten Typ eines bestimmten Programms ohne Typanmerkungen abzuleiten. Der Wikipedia-Artikel ist lesenswert. λW
Martin Berger