我想创建一个 lambda 演算函数 P 这样(P x y z)
给出((x y)(x P)(P z))
. 我曾尝试使用 Y-combinator/Turing 组合器的变体,即 formλg.(g g)
的函数,因为我需要重现函数本身,但我看不到任何前进的方向。任何帮助将不胜感激。
问问题
1156 次
2 回答
2
基本上你想解决 "β-equation" P x y z = (x y) (x P) (P z)
。有一种求解形式方程的一般方法M = ... M ...
。您只需将右侧包装在 lambda 中,形成一个 term 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)
量子点
于 2016-04-18T18:01:13.750 回答
1
U-combinator应该帮助你创建一个自引用的 lambda 抽象。
这是 Ω,最小的非终止程序,很好地展示了 U 组合子。
((λf. (f f))
(λf. (f f)))
如果你能给它一个名字
Ω := λf.(f f)
这是您的抽象可能看起来的样子
((λP. (P P x y z))
(λP. λx. λy. λz. ((x y) (x P) (P z))))
或使用 Ω
λx. λy. λz. Ω (λP. λx. λy. λz. ((x y) (x P) (P z))) x y z
于 2016-04-18T16:54:03.873 回答