Type_inhabitation
で型理論の枝数学的なロジック、与えられた型指定された計算では、タイプの生息問題：この計算のためには、次のような問題であるタイプ与えられました τ { tau}
とタイピング環境 Γ { Gamma}
、存在しますか λ { lambda}-そのような用語M Γ ⊢ ： τ { Gamma vdash M： tau}
？空のタイプの環境では、そのようなMはの住民であると言われています τ { tau}コンテンツ
1 論理との関係
2 正式なプロパティ
3 も参照してください
4 参考文献
論理との関係
以下の場合には、単に型付きラムダ計算、タイプがあれば住民を有し、その場合にのみ、対応する命題はトートロジー最小含意論理。同様に、システムFタイプには、対応する命題が2階述語論理のトートロジーである場合にのみ住民がいます。
ジラールのパラドックスは、住性がカリー・ハワード対応の型システムの一貫性と強く関連していることを示しています。健全であるためには、そのようなシステムは無人のタイプを持たなければなりません。
正式なプロパティ
ほとんどの住性結石では、住性の問題は非常に困難です。リチャード・スタットマンは、単純に型付きラムダ計算の場合、住性の問題はPSPACE-completeであることを証明しました。システムFのような他の結石の場合、問題は決定不可能ですら
も参照してください
カリーハワード同形性
参考文献
^ Pawel Urzyczyn（1997）。「型付きラムダ計算（構文的アプローチ）の居住」。コンピュータサイエンスの講義ノート。スプリンガー：373–389。 Γ ⊢ ： Int { Gamma vdash x：{ text {Int}}}
このプログラミング言語理論または型理論関連
“