22/12/01 11:05:47.61 kl2o24qP.net
>>288
つづき
URLﾘﾝｸ(ja.wikipedia.org)
カリー＝ハワード同型対応
カリー＝ハワード同型対応（カリー＝ハワードどうけいたいおう、英語: Curry?Howard correspondence）とは、プログラミング言語理論と証明論において、計算機プログラムと証明との間の直接的な対応関係のことである。「プログラム＝証明」(proofs-as-programs)・「型＝命題」(formulae-as-types)などとしても知られる。
通常はこの論理と計算の関連性はカリーとハワードに帰属される。しかしながら、このアイデアはブラウワー、ハイティング、コルモゴロフらが定式化した直観主義論理の操作的解釈の一種（ブラウワー＝ハイティング＝ コルモゴロフ解釈（BHK 解釈）（英語版））と関係している。[要出典]
自然演繹とラムダ計算との間の対応
ハスケル・カリーがヒルベルト流の体系とコンビネータ論理の構文的対応を強調した後、ウィリアム・アルヴィン・ハワードは1969年に単純型付きラムダ計算と自然演繹との構文的な同型性を明確にした。以下、左辺で直観主義的自然演繹の含意断片を形式化し、右辺でラムダ計算の型付け規則を示す。
ハワードの対応は自然演繹およびラムダ計算の拡張に対しても自然に延長できる。網羅的ではないがここに列挙しておく：
・グロタンディーク位相に於ける局所真理(▽)様相、あるいは同じことだが Benton, Bierman, and de Paiva (1998) のlax様相(〇)は計算型を記述するCL論理と対応する。[2][3]
BHK解釈
BHK解釈は直観主義的な証明の含意と全称化を関数として解釈するが、解釈における関数のクラスがどのようなものであるかを指定してはいない。もし関数のクラスとしてラムダ計算を取るならば、BHK解釈は自然演繹とラムダ計算との間の対応と同じことを述べていることになる。
カリー＝ハワード＝ランベック対応
ヨアヒム・ランベックは1970年始めに直観主義命題論理とデカルト閉圏の等式理論と対応するある種の型付きコンビネータとの対応関係の証明を示した。このカリー＝ハワード＝ランベック対応は直観主義論理、型付きラムダ計算およびデカルト閉圏との間の対応として知られる。
(引用終り)
以上