Gibt es eine turende, typisierte Lambda -Berechnung?

Question

Gibt es eine Turing Complete typed Lambda Calculi? Wenn ja, was sind einige Beispiele?

Answer 1

Ja sicher. Viele typisierte Lambda -Kalkül akzeptieren nur stark normalisieren Begriffe, so entworfen, können sie keine willkürlichen Berechnungen ausdrücken. Aber ein Typsystem kann alles sein, was Sie mögen. Machen Sie es breit genug, und Sie können alle deterministischen Berechnungen ausdrücken.

Ein triviales Typsystem, das ein turbetontes Fragment des Lambda-Kalküls umfasst Top -Typ). $$ dfrac {} { gamma vdash m: top} $$

Praktischer sind praktisch statisch typisierte funktionale Programmiersprachen im Kern einen typisierten Lambda -Kalkül, der a erlaubt Fixpoint -Kombinator als gut gespielt. Beginnen Sie zum Beispiel mit dem Einfach tippte Lambda -Kalkül (oder das ML -Typ -System oder System f oder ein anderes Typ Ihrer Wahl) und fügen Sie eine Regel hinzu, die einen Fixpoint -Kombinator wie $ mathbf {y} = lambda f macht. ( lambda x. f (x , x)) ( lambda x. f (x , x)) $ gut -ped. $$ dfrac { gamma vdash f: t rightarrow t} { gamma vdash mathbf {y} , f: t} qquad dfrac { gamma vdash f: t rechts t {{{{{{{{ {{{{ {{{ {{{ Gamma vdash ( lambda x. F (x , x)) ( lambda x. F (x , x)): t} $$ Die oben dargestellten Regeln sind eher ungeschickt, da sie Begriffe wie $ machen mathbf {y} , f $ gut gespielt, obwohl ihre Wähler nicht gut gespielt sind-sie sind nicht vollständig kompositorisch. Eine einfache Lösung besteht darin, einen Fixpoint -Kombinator als Sprachkonstante hinzuzufügen und eine Delta -Regel dafür bereitzustellen. Dann ist es einfach, ein Typsystem und eine Reduktionssemantik mit zu haben Geben Sie Erhaltung ein. Sie entkommen vom reinen Lambda -Kalkül in den Bereich des Lambda -Kalküls mit Konstanten. $$ begin {sammeln*} dfrac {} { gamma vdash textbf {fix}: (t rightarrow t) rightarrow t} textbf {fix} , f to f ( textbf { fix} , f) end {samm*} $$

Ein interessantes Typsystem ist der Lambda -Kalkül mit Kreuzungstypen.

$$ dfrac { gamma vdash m: t_1 quad gamma vdash m: t_2} { gamma vdash m: t_1 kedge t_2} ( kedge i) qquad qquad dfrac {{{{{ gama vdash m: top} ( top i) $$

Kreuzungstypen haben interessante Eigenschaften in Bezug auf Normalisierung:

• Eine Lambda-Term kann ohne Verwendung der $ top i $ regel tippt werden, die es stark normalisiert.
• Ein Lambda-Term lässt einen Typ zu, der nicht $ top $ iff hat, es hat eine normale Form.

Sehen Charakterisierung von Lambda-Terrmen mit Gewerkschaftstypen Für einen Einblick, warum Schnitttypen einen so bemerkenswerten Bereich haben.

Sie verfügen also über ein Typsystem, das eine Turing-Complete-Sprache definiert (da jeder Begriff gut angepasst ist) und eine einfache Charakterisierung der Beendigung von Berechnungen. Da dieses Typensystem die Normalisierung charakterisiert, ist es natürlich nicht lehnte.

_{Eine Bemerkung zu den Regel nennt $ ( top i) $ und $ ( Wedge i) $: Sie haben keine formelle Bedeutung, aber sie werden absichtlich ausgewählt. Das $ i $ steht für „Einführung“, da dies Einführungsregeln sind - sie führen das Symbol ($ Wedge $ oder $ top $) in den Typ unterhalb der Zeile ein. Doppelte finden Sie Eliminierungsregeln, wenn ein Symbol über der Zeile, jedoch nicht unten erscheint. Beispielsweise ist die Regel, einen Lambda-Ausdruck im Lambda Calculus einfach zu typisieren, die Einführungsregel für $ rightarrow $, und die Regel, eine Anwendung zu typten, ist die Eliminierungsregel für $ rightarrow $.}