ラムダ計算
計算論 計算可能性とラムダ計算 コンピュータサイエンス大学講座 高橋 正子 (著) 近代科学社 ISBN 4764901846 (1991)
ハロルド・エイブルソン、ジェラルド・ジェイ・サスマン、ジュリー・サスマン共著『計算機プログラムの構造と解釈 第二版』和田英一訳、ピアソンエデュケーション、2000、ISBN 4-8947-1163-X
この記事は2008年11月1日以前にFree On-line Dictionary of Computingから取得した項目の資料を元に、GFDL バージョン1.3以降の「RELICENSING」(再ライセンス) 条件に基づいて組み込まれている。
β-変換は停止しない(無限ループに陥る)場合がある。例えば次の式を適用する場合には停止しない。
(λx. x x) (λx. x x) → (λx. x x) (λx. x x) → ...
ある種のラムダ計算の体系では、任意のラムダ式に対してβ-変換の停止性が保証されていることがある。どのような順序でβ-変換を行ったとしてもβ-変換が停止する性質を強正規化性といい、β-変換の順序を上手く選んだ場合にβ-変換が停止する性質を弱正規化性という。チャーチ・ロッサー性を満たし、かつ停止性を持つラムダ計算の体系では、ラムダ式をどのような順序で評価しても必ず同じ結果になることがわかる。
強正規化的であり、かつ弱チャーチ・ロッサー性を持つラムダ計算の体系はチャーチ・ロッサー性を持つ(ニューマンの補題(英語版))。
型無しラムダ計算の体系では、ある式の停止性を判断する事は決定不能であることが証明されている。
ピーター・ランディン(英語版)は1965年に発表したA Correspondence between ALGOL 60 and Church's Lambda-notationにおいて、ラムダ計算が手続的な抽象化と手続き(サブプログラム)の適用のしくみを提供しているがために、多くのプログラミング言語がラムダ計算にその基礎を置いているとみることができるとしている。
ラムダ計算をコンピュータ上に実装するには、関数を第一級オブジェクトとして取り扱う必要があり、これはスタック・ベースのプログラミング言語においては問題となってくる。これはFunarg問題(英語版)として知られている。
ラムダ計算と最も密接な関係をもつプログラミング言語は関数型言語と呼ばれる諸言語で、本質的にはいくつかの定数とデータ型を用いてラムダ計算を実装している。Lispでは関数の定義にラムダ記法の一変形を用いており、さらに、純Lispと呼ばれるLispのサブセットはラムダ計算と真に等価になっている。
関数を第一級オブジェクトとして扱えるのは関数型言語だけというわけではない。