上述したチャーチ数である。して、評価の例を見てみよう。2)))...アルゴリズムの構造が再帰的に評価されているのがわかるだろう。用いることで全ての再帰的な関数をラムダ式で表現することができる。自然数に対する除算、乗算や比較述語を再帰を用いてよりきれいに定義することができる。存在すること、と定義することができる。対応するチャーチ数によるラムダ式である。この定義は、計算可能性を定義する多くの方法のうちのひとつである。詳しくは、チャーチ-チューリングの提唱の項を見よ。同値性の決定不可能性編集2つのラムダ式を入力とし、それらが同値であるかどうかを判定するアルゴリズムは存在しない。これは決定不可能性が示された歴史的に最初の問題である。ここで使われる「アルゴリズム」という言葉も、もちろんきちんと定義されなければならない。チャーチは自身の証明の中で帰納的関数をその定義に用いたが、現在ではこれは適切なその他のアルゴリズムの定義と等価であることが知られている。チャーチの証明ではこの問題を、あたえられたラムダ式に正規形が存在するかどうかという問題に帰している。正規形とは、それ以上簡約のできない同値なラムダ式のことである。チャーチの証明ではまず、この問題が決定可能である、つまり、ラムダ式で表現可能であると仮定する。それ自身を表すゲーデル数に適用すると矛盾が導かれる。詳しくいえば次のようである。X}を正規形の存在性を判定するラムダ式とする。N}を自然数からそれを表すラムダ式の表現のゲーデル数を求める関数を表すラムダ式とする。x}のゲーデル数を表すラムダ式の表現である。