ラムダ計算 とは？

関数の抽象化と適用を中心に、計算を数学的に表すための体系だよ。基本の式は変数、関数を表すλx.M、関数へ引数を渡すM Nの3種類。プログラミング言語の関数や評価の仕組みを考える理論的な基盤の一つなんだ。

「xを受け取り、そのxを返す関数」だよ。たとえば(λx.x) yでは、本体のxへ引数yを代入してyになる。この計算をβ簡約と呼ぶ。複雑な式では、別の関数に束縛されている変数まで置き換えたり、引数の自由変数を捕まえたりしないようにするんだ。

できるよ。純粋なラムダ計算には数や足し算の記号が最初からあるわけではなく、数も関数で表す。たとえばチャーチ数の2はλf.λx.f(f x)で、fを2回適用することを表すよ。λx.x+1のような例は算術を加えた略記としては便利だけれど、そのまま純粋な体系の基本構文ではないんだ。

関数を作って適用する考え方はつながっているよ。Pythonのlambda x: x + 1や、JavaScriptの(x) => x + 1は匿名関数の例。ただし、それぞれの言語には数や型、副作用などの独自の仕組みがあるので、構文や実行規則がそのまま純粋なラムダ計算と同じというわけではないんだ。

型なしラムダ計算とチューリングマシンは、計算できるものの範囲が同じだと示されているよ。これは速さや、どんな式も計算が終わるという保証ではない。一方、チャーチ＝チューリングのテーゼは、直感的に手順で計算できるものをこうした形式的なモデルで捉えられる、という主張で、モデル間の同等性の定理とは区別するんだ。