ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


ラムダ計算


ヨミ: ラムダケイサン
掲示板をミル!
3カキコ!

ラムダ計算(lambda calculus)とは、何でも関数を用いて計算してしまう方法である。


概要


ラムダ計算とは、関数についての3つの操作だけであらゆる計算が可、すなわちチューリング完全を実現できるという理論である。LISPをはじめとする関数型言語理論的根拠となっている。1930年代Alonzo Churchという数学者が提唱したが、最初に思いついたのはAlonzo Churchではないらしい。

ラムダ計算は以下の3つの操作からなる。きちんと説明しようとするとよくわからない記号だらけになるので、おおざっぱにだけ記載しておく。

η変換は何を当たり前のことを言っているんだと思うかもしれないが、たとえば1からnまでの整数の和をめるのに、1から順番に数を足していく方法でも、等差数列の和の公式を使う方法でも、計算方法は違えど同値であるということである。


ラムダ式


上記操作においては、関数も数値と同じように引数にしたり戻り値にしたりできる、高階関数が前提となっている。このため、数値がx = 1というような書き方ができるように、関数も名前をつけて置き換えられる必要がある。

Alonzo Church自身は、たとえば f(x) = x2 + x + 1 のときに、関数 f 自体を f = λx.(x2 + x + 1) といった書き方をしており、これをラムダ式(lambda expression)と呼んだ。

プログラミングにおいては使用できる文字の制約などにより上記とは少し異なる記法を採用していることがほとんどだが、実質的には同じことなのでそれらもラムダ式と呼ばれている。


名前の由来


ラムダ式に用いられる記号 λ に由来するわけだが、この λ 自身の由来については2説あり、偽についてはあまりはっきりしていない。


由来がある説


Rosserという人が1984年に以下のように報告している。

Russell と Whiteheadが、関数を抽化するときの記号に「^x(HTML仕様上表記できないが、âのaをxにしたもの)」を用いていた。Alonzo Churchは、この表記法にちなんで、「∧x」という記号を使用するようになった。その後印刷しやすいように「∧」の代わりに「λ」を使用するようになった(ちなみにλの大文字Λ(≠∧)である)。


由来なんかない説


Alonzo Church自身は後年「とにかく記号が必要だったからたまたまλを選んだ」とっており、この話を信じるなら特に由来はないということになる。一般には面で報告された「由来がある説」の方が信頼性が高いということになるが、面とはいえ他人がした報告である。一方こちらはAlonzo Church本人の言葉であり、そう聞いた人が1人だけというわけでなく2人いるということなので、こちらもそれなりに信憑性が高い。


関連項目



関連商品


■az4764901846
■az4781911358


最終更新日: 16/11/20 21:16
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ