計算可能性とラムダ計算
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/04/12 16:37 UTC 版)
「ラムダ計算」の記事における「計算可能性とラムダ計算」の解説
自然数から自然数への関数 F: N → N が計算可能であるということは、全ての自然数の対 X, Y に対して F(X) = Y と f x == y が同値となるようなラムダ式 f が存在すること、と定義することができる。ここで、 x, y はそれぞれ X, Y に対応するチャーチ数によるラムダ式である。この定義は、計算可能性を定義する多くの方法のうちのひとつである。より詳しくは、チャーチ-チューリングの提唱の項を見よ。
※この「計算可能性とラムダ計算」の解説は、「ラムダ計算」の解説の一部です。
「計算可能性とラムダ計算」を含む「ラムダ計算」の記事については、「ラムダ計算」の概要を参照ください。
- 計算可能性とラムダ計算のページへのリンク