ニューマン は チューリング を プリンストン大学 に 行か せ 、 同じ 問題 を ラムダ 計算 で 定式 化 し て い た アロンゾ・チャーチ に 会わ せ て も いる 。

コンビネータ 論理 は ラムダ 計算 の 変種 として も 見る こと が できる 。

ラムダ 式 ( ラムダ 抽象 ) は 、 束縛 変数 の ない 原始 的 な 関数 「 コンビネータ 」 の 有限 集合 によって 置き換え られる 。

ラムダ 式 を コンビネータ 式 に 変換 する の は 簡単 で あり 、 また コンビネータ の 簡約 は ラムダ の 簡約 より も シンプル で ある 。

ラムダ 計算 は 、 ラムダ 項 と 呼ば れる 以下 の よう な 形 の 記号 の 列 に 関係 し て いる 。

特定 の 引数 の 平方 を 求める ため に 、 3 を あてる と 、 仮 引数 の 場所 に 3 を 入れる : すべて の 計算 が 、 ラムダ 抽象 と 適用 を 基本 と し た 変数 の 置き換え の シンプル な 概念 で 表現 できる こと は 、 おそらく 驚く べき こと で ある 。

しかし 、 さらに 目覚ましい の は 、 ラムダ 抽象 も 必要 が ない こと で ある 。

コンビネータ 論理 は ラムダ 計算 と 同等 の モデル だ が 、 ラムダ 抽象 は 存在 し ない 。

ラムダ 計算 で の 式 の 評価 は 非常 に 複雑 で ある ( 置換 の 意味 論 は 変数 を 捉える の を 避ける ため の かなり の 気配り と共に 決め なけれ ば なら ない )。

ラムダ 抽象 が 関数 を 作る ため の 唯一 の 方法 だ から 、 コンビネータ 計算 の 中 で は 何 か が それ を 置き換え ね ば なら ない 。

コンビネータ 計算 は 、 ラムダ 抽象 の 代わり に 、 原始 的 な 関数 の 有限 集合 を 提供 する 。

原始 的 関数 は コンビネータ 、 もしくは 、 自由 変数 を 含ま ない ラムダ 項 で ある 。

( S ( K ( S I )) ( S ( K K ) I )) という 表現 は 、 ラムダ 項 として の 表現 λ x . λ y .( y x ) より も はるか に 長い 。

普通 、 T [ ] は ラムダ 項 を Θ ( n 2 ) に 展開 する 。

λ x .( E ₁ E ₂ ) は a という 引数 を 取り 、 ラムダ 項 ( E ₁ E ₂ ) の x を 置き換え て ( E ₁ E ₂ )[ x : = a ] を 生成 する 関数 で ある 。

すべて の コンビネータ が すべて の ラムダ 項 と 外延 的 に 等しく なる よう な one - point bases が 存在 する 。

これら の コンビネータ は 述語 論理 や ラムダ 計算 を コンビネータ 式 に する 際 に 非常 に 有用 で ある 。

コンビネータ の 項 から ラムダ 項 へ の 変換 L [ ] は 自明 で ある 。

なお 、 UCLA 在学 中 は ラムダ ・ カイ ・ アルファ の フラタニティ だっ た 。

チャーチ の 計算 の システム は 発展 し て ラムダ 計算 と なり 、 一方 チューリングマシン は 多 目的 計算 装置 の 標準 的 な モデル と なっ た 。