チューリング完全なタイプのラムダ計算が存在しますか？

Question

チューリングの完全なタイプのラムダ計算はありますか？もしそうなら、いくつかの例は何ですか？

Answer 1

はい、確かに。多くのタイプされたLambda calculiは受け入れます 強く正規化 設計による用語では、任意の計算を表すことができません。しかし、タイプシステムはあなたが好きなものにすることができます。それを十分に広くし、すべての決定論的計算を表現できます。

ラムダ計算のチューリング複雑なフラグメントを含む些細なタイプシステムは、すべての用語をよく型タイプとして受け入れるものです（ トップタイプ）。 $$ dfrac {} { gamma vdash m： top} $$

より実際には、静的にタイプされた機能的プログラミング言語は、そのコアにタイプされたラムダ計算を持っています。 FixPointコンビネーター よくタイプ。たとえば、から始めます 単にLambda計算を入力しました （またはMLタイプシステムまたは システムf または選択した他のタイプシステム）および$ mathbf {y} = lambda fのようなfixpointコンビネーターを作成するルールを追加します。 （ lambdax。f（x 、x））（ lambdax。f（x 、x））$ welltyped。 $$ dfrac { gamma vdash f：t rightarrow t} { gamma vdash mathbf {y} 、f：t} qquad dfrac { gamma vdash f：t rightarrow t} { gamma vdash（ lambdax。f（x 、x））（ lambdax。f（x 、x））：t} $$上記のルールはかなり不器用です。 Mathbf {y} 、f $井戸型は、その構成要素がよくタイプではありませんが、完全に組成されていません。簡単な修正は、Fixpoint Combinatorを言語定数として追加し、Deltaルールを提供することです。次に、タイプシステムと削減セマンティクスを持っていることは簡単なことです タイプ保存. 。純粋なラムダ計算から、定数を持つラムダ微積分の領域に逃げます。 $$ begin {gracking*} dfrac {} { gamma vdash textbf {fix}：（t rightArrow t） rightArrow t} to 、f to f（ textbf {{ textbf { fix} 、f） end {gracking*} $$

純粋なラムダ微積分に固執すると、興味深いタイプシステムは、交差点のあるラムダ計算です。

$$ dfrac { gamma vdash m：t_1 quad gamma vdash m：t_2} { gamma vdash m：t_1 wedge t_2}（ wedge i） qquad qquad dfrac {} { gamma vdash m： top}（ top i）$$

交差タイプには、正規化に関して興味深い特性があります。

• Lambda-Termは、$ top i $ルールを使用することなく入力できます。
• Lambda-Termは、通常のフォームを持っている$ top $ iffを含む型を認めています。

見る 組合タイプを持つラムダテルムの特性評価 交差点タイプがこのような驚くべき範囲を持っている理由についての洞察のためです。

したがって、チューリングコンプリート言語（すべての用語が十分にタイプであるため）を定義するタイプシステムと、終了計算の単純な特性評価があります。もちろん、このタイプシステムは正規化を特徴づけるため、決定できません。

_{ルール名$（ top i）$ and $（ wedge i）$：$：それらは正式な意味はありませんが、意図的に選択されています。 $ i $は「はじめに」の略です。なぜなら、これらは導入ルールであるため、シンボル（$ wedge $または$ top $）をラインの下のタイプに導入します。二重に、シンボルが行の上に表示されるが下ではない場合、排除ルールが見つかります。たとえば、シンプルなラムダ計算でラムダ式をタイプ化するルールは、$ rightArrow $の導入ルールであり、アプリケーションをタイプチェックするルールは$ rightArrow $の排除ルールです。}