Was macht Typ-Inferenz für abhängige Typen unentscheidbaren?

Question

Ich habe es erwähnt, dass abhängige Typ-Systeme sind nicht inferable, aber sind überprüfbar.Ich Frage mich, ob es eine einfache Erklärung, warum das so ist, und ob oder nicht, gibt es eine Begrenzung der "Abhängigkeit", in dem Typen indiziert werden können, die durch die Werte, unter denen eine Art Inferenz möglich ist und oben was ist es nicht?

Answer 1

Für eine ziemlich einfache version der abhängigen Typ-Theorie, Gilles Dowek gab einen Beweis der nicht-entscheidbarkeit des typability in ein nicht-leerer Rahmen:

Gilles Dowek, Die Unentschiedenheit der typability in der $\lambda\Pi$-calculus

Finden hier.

Lassen Sie mich zuerst klären, was bewiesen ist, wird in diesem Papier:er zeigt, dass in einem abhängigen Rechnung ohne Anmerkungen zu den Abstraktionen, es ist unentscheidbaren zu zeigen typeability ein Begriff in einer nicht-leeren Rahmen.Diese beiden Hypothesen sind notwendig:in den leeren Rahmen, typability reduziert, dass der einfach typisierte $\lambda$-calculus (entscheidbar von Hindley-Milner) und mit den Anmerkungen auf die Abstraktionen, die übliche Art-directed-Algorithmus gilt.

Die Idee ist zu Kodieren eine Post correspondence problem, als eine Art Bekehrung problem, und dann sorgfältig Konstrukt, ein Begriff, typeable iff die zwei spezifische Typen umgewandelt werden.Dies setzt die Kenntnis der Form, die von den normalen Formen, die immer vorhanden sind in diesem Kalkül.Der Artikel ist kurz und gut-geschrieben, so dass ich nicht mehr ins detail gehen, hier.

Jetzt in der polymorphe ule, wie z.B. system-F, es wäre schön, in der Lage sein, auf den Typ zu schließen Abstraktionen und Anwendungen, ohne die Anmerkungen, die auf $\lambda$s wie oben.Dies ist auch unentscheidbaren, aber der Beweis ist viel schwieriger, und die Frage war, öffnen Sie für einige Zeit.Die Angelegenheit wurde gelöst, indem Brunnen:

J.B.Wells, Typability und geben Sie Check-in System F sind äquivalent und unentscheidbaren.

Diese finden Sie hier.Alles was ich weiß ist, dass es reduziert das problem der semi-Vereinigung (die Vereinigung modulo Instanziierung der universellen Quantoren, und unentscheidbaren) Typ Check-in-System F.

Schließlich ist es ziemlich einfach zu zeigen, dass die Besiedlung des abhängigen Familien ist unentscheidbaren:einfach codieren Sie ein Post-problem in den Konstruktor Indizes. Hier einige Folien von Nicolas Oury, daß sketch das argument.

Ob es ist eine "Grenze", es hängt viel davon ab, was Sie versuchen zu tun mit abhängigen Typen, und es gibt viele Annäherungen, die werden versuchen, entweder entscheidbar, oder zumindest nahe genug, um nutzbar zu sein.Diese Fragen sind immer noch sehr viel ein Teil der aktiven Forschung, obwohl.

Ein möglicher Weg ist der Bereich der "Verfeinerung Typen", wo die Sprache der expression von Typ-Abhängigkeiten eingeschränkt zu ermöglichen entscheidbar Prüfung sehen, z.B. Flüssigkeit Arten.Es ist selten, dass eine vollständige Typ-Inferenz ist entscheidbar, auch in diesen Systemen zwar.