john7rv

ラムダ計算とは一言で言えば
数学の計算をすべて１種類の関数の組み合わせだけで表現しようとする
考えです
例えば我々の日常の周りの物は机でもパソコンでもどんな複雑なものでも物質は究極的にはすべて膨大な数の原子でできており
原子の組み合わせだけでできてます
それと同じように
どんな複雑な計算でも究極的には実は多くのラムダ式の組み合わせだけで表現できるとする試みです
その計算の原子とする数学の最小単位は
たった一つの引数を持つ関数でありチャーチはこれをラムダ式と名付けました

((λx.x + 10) 2)

上のλ式は

2 + 10

の計算を表しています
１種類の関数だけですべてを表すなど無理ではないかと
思うかもしれませんが
例えば数などもチャーチ数を使いラムダ関数で表現でき
複数の引数はカリー化を使うことで
１引数に変換できます
ループは不動点演算子を使うことで可能です

チャーチがこのようなものを思いついたのは
計算とはなにかその性質を表そうとしたからです
複雑なものを最も単純な形にすることで
その性質を知ることができます

ラムダ計算は主にチャーチによって作られました
20世紀初頭は数学の基礎に関する研究が非常に盛んになった時期です。
それまで漠然と考えられた数学つまり計算というものが一体何なのか？
何ができて何ができないのかを本格的に考えることになり、
そのためのモデルのようなものが必要になりました
その最も有名で成功したものがチューリングによるチューリングマシンです
計算とはなんなのかという問いに
計算(アルゴリズム)とはチューリング・マシンにできることだと答えることができるようになったのです
チューリング・マシンは後にコンピューターの原型となりました
しかしチューリング・マシン以外にも多くのものが考えられラムダ計算もそのひとつです
それ以外にも帰納関数(再帰関数)もあります
チューリング・マシンも帰納関数もラムダ計算も別々に考えられたものですが
後に全く同じものを指していることがわかりました
チューリング・マシンの操作の全ては帰納関数で置き換えることができます
また帰納関数もすべてラムダ計算で表現可能です
全てはつながっていたのです

そこからチャーチ・チューリングのテーゼが導かれます
数学にできることはチューリング・マシン(コンピューター)にでき
チューリング・マシン(コンピューター)にできないことは数学にもできない
と言うことができます