コンビネータ論理
計算機科学において(計算可能性理論や証明論で)は、コンビネータ論理は計算を単純化したモデルとして使われる。単純にもかかわらず、コンビネータ論理は計算の本質的な特徴をとらえている。
コンビネータ論理はラムダ計算の変種としても見ることができる。ラムダ式(ラムダ抽象)は、束縛変数のない原始的な関数「コンビネータ」の有限集合によって置き換えられる。ラムダ式をコンビネータ式に変換するのは簡単であり、またコンビネータの簡約はラムダの簡約よりもシンプルである。したがってコンビネータ論理は非正格関数型言語やGraph reduction machineのモデルとして使われている。もっとも純粋な形は、唯一のプリミティブが入出力のために拡張されたSとKのコンビネータの、Unlambdaというプログラミング言語である。実用的なプログラミング言語ではないが、Unlambdaは理論的な関心がある。
コンビネータ論理は解釈の多様性を与えられる。カリーによる論文では、どのように従来の論理のための公理をコンビネータ論理の等式にするかを示した。デイナ・スコットは、60,70年代にどのようにしてモデル理論とコンビネータ論理を結びつけるかを示した。
SとKが外延的にすべてのラムダ項と同値なものに合成されうるのは、おそらく驚くべき事実である。したがって、チャーチのテーゼによれば、それはあらゆる計算可能な関数に合成されうる。その証明は、T[ ]という任意のラムダ項を同値なコンビネータにする変換を示すことで与えられる。 T[ ]は以下のように定義する。
T[x] => x
T[(E1 E2)] => (T[E1] T[E2])
T[λx.E] => (K T[E]) (if x does not occur free in E)
T[λx.x] => I
T[λx.λy.E] => T[λx.T[λy.E]] (if x occurs free in E)
T[λx.(E1 E2)] => (S T[λx.E1] T[λx.E2])
これはabstraction eliminationとして知られている。
T[ ]変換によって生成されたコンビネータはη-reductionによって小さくなりうる。
λx.(E x)はxを引数にとり、Eを適用する関数である。それは外延的にはE自身と同値である。それはつまりEをコンビネータの形にすれば十分である。 この例は、この簡略化を根拠付ける。
このコンビネータはより早く、長いものと同値である。
同様に、もとのT[ ]はλf.λx.(f x)を(S (S (K S) (S (K K) I)) (K I))に変換したが、η-簡約を用いればλf.λx.(f x)はIに変換される。