How many possible Beta-reductions considering order of the expression $(\lambda x.\lambda y.y)(\lambda x.x) ((\lambda x.x) (\lambda y.y))$ - Mathematics Stack Exchange most recent 30 from math.stackexchange.com 2019-12-05T17:48:38Z https://math.stackexchange.com/feeds/question/2993236 https://creativecommons.org/licenses/by-sa/4.0/rdf https://math.stackexchange.com/q/2993236 2 How many possible Beta-reductions considering order of the expression $(\lambda x.\lambda y.y)(\lambda x.x) ((\lambda x.x) (\lambda y.y))$ IntegrateThis https://math.stackexchange.com/users/270702 2018-11-10T23:01:05Z 2018-11-11T01:23:25Z <p>Here is a lamba calculus expression:</p> <p><span class="math-container">$(\lambda x.\lambda y.y)(\lambda x.x)((\lambda x.x) (\lambda y.y))$</span></p> <p>For simplicity let </p> <p><span class="math-container">$a:=(\lambda x.\lambda y.y)$</span></p> <p><span class="math-container">$b:=(\lambda x.x)$</span></p> <p><span class="math-container">$c:=(\lambda x.x)$</span></p> <p><span class="math-container">$d:=(\lambda y.y)$</span></p> <p>Then I can re-write the expressions as evaluating <span class="math-container">$(a)(b)((c)(d))$</span>, and I wish to compute how many different ways I can evaluate this expression using beta-reduction (which I am then supposed to write out). At first impulse I would think there would be <span class="math-container">$4!=24$</span> ways to do this by simply choosing all orderings of <span class="math-container">$a,b,c,d$</span> evaluations, but this seems like too many results ( now that I think about it I even see that it could be 5!). Any hints appreciated, there is something I am not understanding about the order of evaluations in Beta Reductions.</p> <p>I also know that Beta-reductions are left associative, so the initial expression is equivalent to : <span class="math-container">$((\lambda x.\lambda y.y)(\lambda x.x))((\lambda x.x) (\lambda y.y))$</span></p> https://math.stackexchange.com/questions/2993236/-/2993339#2993339 2 Answer by SpooFwen for How many possible Beta-reductions considering order of the expression $(\lambda x.\lambda y.y)(\lambda x.x) ((\lambda x.x) (\lambda y.y))$ SpooFwen https://math.stackexchange.com/users/510477 2018-11-11T01:06:47Z 2018-11-11T01:23:25Z <p>There are only three ways to evaluate this. The first step is either evaluating the <span class="math-container">$$(\lambda x. \lambda y. y)\lambda x. x$$</span> or the <span class="math-container">$$(\lambda x. x)\lambda y. y$$</span>In the first case, you can then choose to evaluate these two ways: <span class="math-container">$$((\lambda x. \lambda y. y)\lambda x. x)((\lambda x. x)\lambda y. y) \to_{\beta}(\lambda y. y)((\lambda x. x)\lambda y. y) \to_{\beta}((\lambda x. x)\lambda y. y) \to_{\beta} \lambda y. y$$</span> or <span class="math-container">$$((\lambda x. \lambda y. y)\lambda x. x)((\lambda x. x)\lambda y. y) \to_{\beta}(\lambda y. y)((\lambda x. x)\lambda y. y) \to_{\beta}((\lambda y. y)\lambda y. y) \to_{\beta} \lambda y. y$$</span> in the second case you only have one way to go, <span class="math-container">$$((\lambda x. \lambda y. y)\lambda x. x)((\lambda x. x)\lambda y. y) \to_{\beta} ((\lambda x. \lambda y. y)\lambda x. x)(\lambda y. y) \to_{\beta} (\lambda y. y)(\lambda y. y) \to_{\beta} \lambda y.y$$</span></p>