如何用 lambda 术语定义带有教会数字的函数？

Question

如何用 lambda 项表达以下函数？

f(n) = T 如果 n != 0。 F 如果 n = 0.

n代表一个教会数字。

我知道 0 := λf.λx.x 其中 λx.x 是恒等函数，所有其他自然数都可以表示为 n := λf.λx.f (f ... (f x)) 其中包含比 0 项多 n 倍的 f。例如。 3 := λf.λx.f (f (f x)).

但是我怎样才能为上面的函数推导出一个有效的 λ 项呢？我想我也需要 y 才能获得 T/F。因此我可以用λf.(λxy.fxy)来表示数字n，对吧？但是 F 和 T 呢？以下是上述函数的正确 λ 项吗？ λf.(λxy.fxy(yFT)) 其中 T=λxy.x 且 F=λxy.y?

Answer 1

不，你 n 的术语。它是一个需要两个参数的函数，一个 f 和一个 z:

isZero n = n ( ;; f, a function, expecting x
               ;;       or the result of (f (f ... (f x) ...))
               λx.
               ;; but we know what we want it to return, always: it is:
                  F    ;; false, for n is _not_ 0
             )
             ( ;; the initial x, in case n is ......... 0!
               ;; so we know what we want it to be, in case n is 0:
               T       ;; true, for n _is_ 0
             )

因此

isZero = λn.n(λx.F)T

如果n为0，isZero n将returnT；否则，F:

{0}(λx.F)T = T
{1}(λx.F)T = (λx.F)T = F
{2}(λx.F)T = (λx.F)((λx.F)T) = F
{3}(λx.F)T = (λx.F)((λx.F)((λx.F)T)) = F
....

如何用 lambda 术语定义带有教会数字的函数？

How to define a function with Church numerals in lambda-terms?

function

lambda-calculus

computation-theory

church-encoding

computability