Gibt es eine typisierte Lambda-Rechnung, die konsistent und vollständig ist?

20

Gibt es eine typisierte Lambda-Rechnung, in der die entsprechende Logik unter der Curry-Howard-Korrespondenz konsistent ist und in der es typisierbare Lambda-Ausdrücke für jede berechenbare Funktion gibt?

Dies ist zugegebenermaßen eine ungenaue Frage, da eine genaue Definition der "typisierten Lambda-Rechnung" fehlt. Ich frage mich im Grunde, ob es entweder (a) bekannte Beispiele dafür oder (b) bekannte Unmöglichkeitsbeweise für etwas in diesem Bereich gibt.

Edit: @cody gibt eine genaue Version dieser Frage in seiner Antwort unten an: Gibt es ein logisches reines Typensystem (LPTS), das konsistent und vollständig ist (in einem unten definierten Sinne)?

Morgan Thomas
quelle
2
Es gibt keinen rekursiv axiomatisierbaren Kalkül (Lambda oder anderweitig), dessen nachweislich gesamte rekursive Funktionen alle rekursiven Funktionen sind, so dass Ihr Kalkül nicht terminierende Terme beinhalten müsste.
Emil Jeřábek unterstützt Monica am
2
Diese Antwort hat einen Satz, der besagt, dass Sie keine Art von Kalkül haben können, die sowohl vollständig als auch vollständig ist.
Andrej Bauer
1
Es wird Ihre Frage wahrscheinlich beantworten, sobald Sie sie ausreichend genau formuliert haben. Ich denke, Andrejs Beweis ist unnötig kompliziert (aber er zeigt mehr): Der Punkt ist einfach, dass wenn es ein effektiv beschriebenes System gäbe, in dem alle rekursiven Funktionen so darstellbar wären, dass Sie syntaktisch bestätigen können, dass ein Ausdruck eine ehrliche Darstellung von a ist Eine rekursive Funktion (z. B. durch Überprüfen, ob sie im System korrekt eingegeben wurde) würde zu einer universellen rekursiven Gesamtfunktion führen, die unmöglich ist.
Emil Jeřábek unterstützt Monica am
1
Natürlich könnte eine klassische Antwort auf diese Art von Frage lauten: typisierte Rechnung mit Schnittpunkttypen , da sie alle (und nur diejenigen) Terme eingibt , die stark normalisieren. Es ist eher eine philosophische Frage, ob der Kalkül eine "Curry-Howard-Interpretation" zulässt oder nicht. λ
Cody
2
Präziser kann man hier kaum sein, denn die Frage ist nicht präzise.
Andrej Bauer

Antworten:

21

In Ordnung, ich werde es kurz ansprechen: Im Allgemeinen gilt für ein gegebenes Typensystem Folgendes:T

Wenn alle gut Typ Begriffe im Kalkül - Normalisieren sind, dann T ist konsistent , wenn sie als Logik betrachtet.TT

Der Beweis erfolgt im Allgemeinen unter der Annahme, dass Sie einen Term vom Typ F a l s e haben , indem Sie die Subjektreduktion verwenden, um eine normale Form zu erhalten, und dann durch Induktion über die Struktur eines solchen Terms fortfahren, um einen Widerspruch zu erhalten.absurdFalse

Es ist natürlich zu fragen, ob das Gegenteil zutrifft, dh

Für jede Art System , wenn T ist logisch konsistent , dann jeder gut getippt Begriff in T ist Normalisieren.TTT

Das Problem dabei ist, dass es keinen wirklich allgemeinsten Begriff von "Typensystem" gibt und noch weniger Übereinstimmung über die Bedeutung der logischen Konsistenz für solche Systeme besteht. Wir können dies jedoch empirisch überprüfen

Für die meisten bekannten Typsysteme, die eine logische Interpretation haben, gilt in der Tat das Gegenteil.

Wie ist dies mit der Vollständigkeit von Turing verbunden? Nun, zum einen zeigt Andrejs Argument , dass eine der folgenden Aussagen zutreffen muss , wenn die Typprüfung entscheidend ist :

  1. Die Menge aller gut getippten Programme stimmt nicht vollständig.
  2. Es gibt ein nicht abschließendes, gut typisiertes Programm.

Dies deutet darauf hin, dass:

Typsysteme, die eine logische Interpretation haben und konsistent und rekursiv aufzählbar sind, sind es nicht Turing abgeschlossen.

Um einen tatsächlichen Satz anstelle eines Vorschlags zu geben, müssen Typensysteme und logische Interpretationen mathematisch präzise formuliert werden.

Nun kommen zwei Bemerkungen in den Sinn:

  1. Es gibt ein unentscheidbares Typsystem, das Schnittpunkttypsystem, das eine logische Interpretation hat und jedes normalisierende Term darstellen kann. Wie Sie bemerken, ist dies nicht ganz das Gleiche wie "Turing Complete", da der Typ einer Gesamtfunktion möglicherweise aktualisiert (genauer definiert) werden muss, bevor er auf das gewünschte Argument angewendet wird. Der Kalkül ist ein "Curry-Stil" -Kalkül und ist gleich STLC + Γ Mλ und ΓΓM:τσ

    ΓM:τΓM:σΓM:τσ
    Es ist klar, dass die "Interpretation"=∧ ist
    ΓM:τσΓM:τΓM:τσΓM:σ
    = zu einer konsistenten logischen Interpretation führt.
  2. Es gibt eine Klasse von Typsystemen, die Pure Type Systems , in denen eine solche Frage präzisiert werden könnte. In diesem Rahmen ist die logische Interpretation jedoch weniger klar. Man könnte versucht sein zu sagen: "Ein PTS ist konsistent, wenn es einen unbewohnten Typ hat". Dies funktioniert jedoch nicht, da Typen möglicherweise in verschiedenen "Universen" leben, in denen einige konsistent sind und andere nicht. Coquand und Herbelin definieren einen Begriff von logischen reinen Typensystemen , in denen die Frage sinnvoll ist und zeigen

    Jedes inkonsistente, nicht abhängige LPTS hat einen Schleifen-Kombinator (und auch Turing Complete).

    Welches beantwortet die Frage in eine Richtung (inkonsistent TC) in diesem Fall. Soweit ich weiß, ist die Frage nach dem allgemeinen LPTS noch offen und ziemlich schwierig.


Bearbeiten: Die Umkehrung des Coquand-Herbelin-Ergebnisses ist nicht so einfach, wie ich dachte! Folgendes habe ich mir bisher ausgedacht.

Ein logisches reines Typensystem ist ein PTS mit (mindestens) den Sortierungen und T y p e , (mindestens) dem Axiom P r o p : T y p e und (mindestens) der Regel ( P r o p , P r o p , P r o p ) , mit der weiteren Voraussetzung, dass es keine Art von P r o p gibt .PropTypeProp:Type(Prop,Prop,Prop)Prop

Jetzt gehe ich von einer bestimmten Aussage zur Vollständigkeit der Prüfung aus: Repariere ein LPTS L and let Γ be the context

Γ=nat:Prop, 0:nat, S:natnat

L is Turing Complete iff for every total computable function f:NN there is a term tf such that

Γtf:natnat
and for every nN
tf (Sn 0)βSf(n) 0

Now Andrej's diagonalization argument shows that there are non-terminating t of type nat.

Now it seems like we are half-way there! Given a non terminating term Γloop:nat, we want to replace occurrences of nat by some generic type A and get rid of 0 and S in Γ, and we will have our inconsistency (A is inhabited in the context A:Prop)!

Unfortunately this is where I get stuck, since it is easy to replace S by the identity, but the 0 is much harder to get rid of. Ideally we would like to use some Kleene recursion theorem, but I haven't figured this out yet.

cody
quelle
OK, so first two clarifications about your remark (1). What do you mean when you say that this system of intersection types is not recursively enumerable? Certainly the set of theorems of the system is r.e., because you've given it as a straightforward sequent calculus. Also, the result I see proven in the paper you linked is that the terms typable in the system are exactly the strongly normalizing terms; but isn't that different from saying that it can type exactly the total computable functions? E.g., isn't λx.xx strongly normalizing, but not total?
Morgan Thomas
Now a question about your remark (2). It looks to me like the theorem you quote is not what we're interested in. It says that for every non-dependent LPTS, if it's inconsistent then it's Turing complete. But we'd like to know whether for every LPTS, if it's Turing complete then it's inconsistent. Am I misunderstanding something here?
Morgan Thomas
@MorganThomas: Ah, you are correct about the first point: what I meant to say is that the type system can not be decidable, that is, given Γ,t,A, the statement Γt:A is undecidable. I'll correct this in the post.
cody
The second point: you are also correct that one can have a non-total function that is well-typed (though one may not necessarily apply it to a given argument). I'll amend the answer.
cody
1
Third point. You are correct again! However the converse (in the special case of LPTS) is rather trivial. I'll outline the argument.
cody
11

Hier ist eine Antwort auf eine Variante von @codys Präzisierung meiner Frage. Es gibt eine konsistente LPTS, die in etwa @ cody's Sinne vollständig ist, wenn wir die Einführung zusätzlicher Axiome und zulassenβ-Reduktionsregeln. Das System ist also streng genommen kein LPTS; es ist nur so etwas wie eins.

Betrachten Sie die Konstruktionsrechnung (oder Ihr Lieblingsmitglied der λ-cube). This is an LPTS, but we're going to add extra stuff which makes it not an LPTS. Choose constant symbols nat,0,S, and add the axioms:

nat:
0:nat
S:natnat

Index the Turing machine programs by natural numbers, and for each natural number e, choose a constant symbol fe, add the axiom fe:natnat, and for all e,xN, add the β-reduction rule

fe(x)βΦe(x),

where as usual Φe(x) is the output of the eth Turing machine program on x. If Φe(x) diverges then this rule doesn't do anything. Note that by adding these axioms and rules the system's theorems remain recursively enumerable, though its set of β-reduction rules is no longer decidable, but merely recursively enumerable. I believe we could easily keep the set of β-reduction rules decidable by spelling out explicitly the details of a model of computation in the syntax and rules of the system.

Now, this theory is clearly Turing complete in roughly @cody's sense, just by brute force; but the claim is that it's also consistent. Let's construct a model of it.

Let U1U2U3 be three sets, such that:

  • ,N,0,SU1 (where S is the successor function).
  • Each set is transitive; if abUi, then aUi.
  • Each set is closed under the formation of function spaces; i.e., if A,BUi, then BAUi.
  • Each set is closed under the formation of dependent products; i.e., if AUi and f:AUi, then aAf(a)Ui.

The existence of such sets follows, for example, from ZFC plus the axiom that every cardinal is bounded by an inaccessible cardinal; we can take each set Ui to be a Grothendieck universe.

We define an "interpretation" to be a mapping v from the set of variable names to elements of U2. Given an interpretation v, we can define an interpretation Iv of terms of the system in the evident way:

  • Iv(x)=v(x), for x a variable name.
  • Iv()=U1,Iv()=U2.
  • Iv(nat)=N,Iv(0)=0,Iv(S)=S.
  • Iv(fe)=Φe, i.e., the function NN defined by the eth Turing program.
  • Iv(AB)=Iv(A)(Iv(B)), if Iv(A) is a function with Iv(B) in its domain, or Iv(AB)=0 otherwise (just an arbitrary choice).
  • Iv(λx:A.B) is the function which maps an element aIv(A) to Iv[x:=a](B).
  • Iv(Πx:A.B)=aIv(A)Iv[x:=a](B).

We have that for all terms A, Iv(A)U3. Now we say that an interpretation v satisfies A:B, written vA:B, if Iv(A)Iv(B). We say that ΓA:B if for all interpretations v, if vx:C for all (x:C)Γ, then vA:B.

It is straightforward to check that if ΓA:B, then ΓA:B, so this is a model of the system. But, for any variables x,y, it is not the case that y:x:y, because we can interpret y by , so the system is consistent.

Now, this is an answer to my original question, in the sense that this is something that it's reasonable to call a typed lambda calulus, which is consistent and Turing complete. However, it's not an answer to @cody's question, because this is not an LPTS, because of the addition of extra axioms and β-reduction rules. I imagine that the answer to @cody's question is much harder.

Morgan Thomas
quelle
2
This is a nice answer, but I'm not sure you need to go through all those calisthenics to prove consistency: a term of type A in the empty context can be "de-sugared" to a term in the CoC: I'll call the fe(x)Φe(x) rules ι-rules and keep β for the usual ones. Perform all β-reductions (this terminates since you have only added constants), and replace every term of the form fe(x) by its reduct if it has one. The idea here is that the ι-rules only operate on ground terms, so you can do all the β-reductions first to get them out of the way.
cody
I think you're right. This is not my field, so I'm a bit clumsy doing things. :-) I think your proof works, and one interesting consequence, if I'm right, is that this theory doesn't have very much consistency strength. It looks like a potentially very powerful theory, since it has types and natural numbers, which should let you interpret set theory; but apparently you can't, because you can prove it consistent without using powerful set theory!
Morgan Thomas