Lambda 微积分 beta 归约
Lambda Calculus beta reduction
我有以下 lambda 演算：
( x ( λyz.xz ) ( λxy.zyx )) (( λyx.xyz ) ( λy.xz ))
我已经减少了：
alpha => ( x ( λyz.xz ) ( λxy.zyx )) (( λyx1.x1yz )) ( λy.xz ))
beta => ( x ( λyz.xz ) ( λxy.zyx )) ( λx1.x1 ( λy.xz ) z )
我的问题：为什么下面的归约是错误的？他们似乎简化了我的表达方式：
beta1 => ( x ( λyz.xz ) ( λxy.zyx )) ( λx1.x1 ( xz ))
beta2 => ( x ( λy.x ( λxy.zyx ))) ( λx1.x1 ( xz ))
为避免混淆，我建议多进行 alpha 重命名。
所以看起来你在 "scope" 中有 x 和 z（它们不受你术语中任何 λ 的约束），最好确定你是否是否指的是他们。
我会这样改写你的术语：
(x (λy1,z1. x z1) (λx2,y2. z y2 x2)) ((λy3,x3. x3 y3 z) (λy4. x z))
重命名我走得很远（当然这是不必要的，但这样，我们就知道哪个是哪个了）。
这个词 beta-reduces 到
(x (λy1,z1. x z1) (λx2,y2. z y2 x2)) ((λx3. x3 (λy4. x z) z))
然后
(x (λy1,z1. x z1) (λx2,y2. z y2 x2)) ((λx3. x3 (λy4. x z) z))
这确实与您所写的 alpha 等效。
然后你要做的是将 (λy4. x z) 应用到 z。
这不是你应该阅读 x3 (λy4. x z) z 的方式，它也可以像 (x3 (λy4. x z)) z 这样用更多的括号写成。
这个术语不知何故被卡住了，因为它的头是一个变量。
您对此无能为力，因为该术语还涉及您无法减少的应用程序。
也许你也可以通过 eta-reduction 将 (λy1,z1. x z1) 重写为 (λy1. x)。
所以你不能得到 (x (λyz.xz) (λxy.zyx)) (λx1.x1 (x z)) 并且出于同样的原因，你不能将它减少到 (x (λy.x (λxy.zyx))) (λx1.x1 (x z)) 因为你把括号弄错了。
f x y 从左到右读取，你取 f 并将其应用到 x，然后将结果应用到 y.
我会保持这个答案非常简单。
要减少到 beta1 或 beta2，请注意您已减少 ( λy.xz ) z in
"x1 ( λy.xz ) z" 就像 "x1 ( ( λy.xz ) z ) "，所以你可以减少。，即 parenthesize/group 最后两个表达式 ( λy.xz ) 和 z 在一起，这是错误的。
这不是它应该的工作方式。在减少 lambda 表达式的同时，您应该保持 左结合性.,
即，始终将最左边的表达式组合在一起，例如“ ( x1 ( λy.xz ) ) z” 而不是 "x1 ( ( λy.xz ) z )" [这是错误的]。
左结合性，如果有E1 E2 E3 E4这样的表达式，
您应该将其分组为 ( ( (E1 E2) E3 ) E4 )
因此，对于 beta2，您不能将 x1 ( λy.xz ) z 减少到 "x1 ( xz )"。 beta1 的逻辑相同。
我希望这对你有意义。
我有以下 lambda 演算：
( x ( λyz.xz ) ( λxy.zyx )) (( λyx.xyz ) ( λy.xz ))
我已经减少了：
alpha => ( x ( λyz.xz ) ( λxy.zyx )) (( λyx1.x1yz )) ( λy.xz ))
beta => ( x ( λyz.xz ) ( λxy.zyx )) ( λx1.x1 ( λy.xz ) z )
我的问题：为什么下面的归约是错误的？他们似乎简化了我的表达方式：
beta1 => ( x ( λyz.xz ) ( λxy.zyx )) ( λx1.x1 ( xz ))
beta2 => ( x ( λy.x ( λxy.zyx ))) ( λx1.x1 ( xz ))
为避免混淆，我建议多进行 alpha 重命名。
所以看起来你在 "scope" 中有 x 和 z（它们不受你术语中任何 λ 的约束），最好确定你是否是否指的是他们。
我会这样改写你的术语：
(x (λy1,z1. x z1) (λx2,y2. z y2 x2)) ((λy3,x3. x3 y3 z) (λy4. x z))
重命名我走得很远（当然这是不必要的，但这样，我们就知道哪个是哪个了）。
这个词 beta-reduces 到
(x (λy1,z1. x z1) (λx2,y2. z y2 x2)) ((λx3. x3 (λy4. x z) z))
然后
(x (λy1,z1. x z1) (λx2,y2. z y2 x2)) ((λx3. x3 (λy4. x z) z))
这确实与您所写的 alpha 等效。
然后你要做的是将 (λy4. x z) 应用到 z。
这不是你应该阅读 x3 (λy4. x z) z 的方式，它也可以像 (x3 (λy4. x z)) z 这样用更多的括号写成。
这个术语不知何故被卡住了，因为它的头是一个变量。
您对此无能为力，因为该术语还涉及您无法减少的应用程序。
也许你也可以通过 eta-reduction 将 (λy1,z1. x z1) 重写为 (λy1. x)。
所以你不能得到 (x (λyz.xz) (λxy.zyx)) (λx1.x1 (x z)) 并且出于同样的原因，你不能将它减少到 (x (λy.x (λxy.zyx))) (λx1.x1 (x z)) 因为你把括号弄错了。
f x y 从左到右读取，你取 f 并将其应用到 x，然后将结果应用到 y.
我会保持这个答案非常简单。
要减少到 beta1 或 beta2，请注意您已减少 ( λy.xz ) z in "x1 ( λy.xz ) z" 就像 "x1 ( ( λy.xz ) z ) "，所以你可以减少。，即 parenthesize/group 最后两个表达式 ( λy.xz ) 和 z 在一起，这是错误的。
这不是它应该的工作方式。在减少 lambda 表达式的同时，您应该保持 左结合性., 即，始终将最左边的表达式组合在一起，例如“ ( x1 ( λy.xz ) ) z” 而不是 "x1 ( ( λy.xz ) z )" [这是错误的]。
左结合性，如果有E1 E2 E3 E4这样的表达式，
您应该将其分组为 ( ( (E1 E2) E3 ) E4 )
因此，对于 beta2，您不能将 x1 ( λy.xz ) z 减少到 "x1 ( xz )"。 beta1 的逻辑相同。
我希望这对你有意义。