我想创建一个 lambda 演算函数 P,使得 (P x y z)
给出 ((x y)(x P)(P z))
。我尝试过使用 Y-combinator/Turing 组合器的变体,即 λg.(g g)
形式的函数,因为我需要重现函数本身,但我看不到任何前进的方向。任何帮助将不胜感激。
最佳答案
基本上你想求解“β方程”P x y z = (x y) (x P) (P z)
。
有一种求解 M = ... M ...
形式的方程的通用方法。
您只需将右侧包裹在 lambda 中,形成一个术语 L
,其中所有出现的 M
都被 m
替换:
L = λm. ... m ...
然后使用定点组合器即可得到解决方案。让我用你的例子来说明一下。
L = λp. (λxyz. (x y) (x p) (p z)),
where λxyz. is a shorthand for λx. λy. λz.
然后,P = Y L
,展开Y
和L
我们得到:
P = (λf. (λg. f (g g)) (λg. f (g g))) (λp. (λxyz. (x y) (x p) (p z)))
->β
(λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)) (λg. (λp. (λxyz. (x y) (x p) (p z))) (g g))
// the previous line is our "unfolded" P
让我们检查一下 P
是否符合我们的要求:
P x y z
= // unfolding definition of P
(λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)) (λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)) x y z
->β
((λp. (λxyz. (x y) (x p) (p z))) ((λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)) (λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)))) x y z
->β
(λxyz. (x y) (x ((λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)) (λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)))) (((λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)) (λg. (λp. (λxyz. (x y) (x p) (p z))) (g g))) z)) x y z
->β
(x y) (x ((λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)) (λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)))) (((λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)) (λg. (λp. (λxyz. (x y) (x p) (p z))) (g g))) z)
= // folding 1st occurrence of P
(x y) (x P) (((λg. (λp. (λxyz. (x y) (x p) (p z))) (g g)) (λg. (λp. (λxyz. (x y) (x p) (p z))) (g g))) z)
= // folding 2nd occurrence of P
(x y) (x P) (P z)
Q.E.D.
关于recursion - 递归 lambda 演算函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36699312/