# Lambda Calculus - Reductions #4

# Lambda Calculus - Reductions #4

- DJ
davidjorna + 0 comments I'm still learning lambda calculus, so please correct me if my logic is wrong. But here is my understanding of the probem:

If you just take the inner part of the expression and apply beta reduction, you get:

(λx.(f (x x)))(λx.(f (x x))) =(f (x x))[x:=(λx.(f (x x)))] =(f ((λx.(f (x x)))(λx.(f (x x)))))

Which is more complex than the original function, so the reduction process doesn't terminate.

dhirajhimani + 0 comments (λg.(λf.((λx.(f (x x)))(λx.(f (x x))))) g) λg.((λx.(g (x x)))(λx.(g (x x)))) λg.((λx.(g x x))(λx.(g x x))) λg.((g λx.(g x x) λx.(g x x))) //Now this falls in recursion which makes it can't solve

- IF
irenelfeng + 1 comment I just guessed on this, but could someone explain how this function does not reduce? Is it just because this expression is at its top level a function (and not a constant or application), therefore, we can't reduce a function?

mattklein999 + 2 comments It's related to the "omega function" solution to the previous problem.

https://en.wikipedia.org/wiki/Lambda_calculus#Beta_reduction

- IF
irenelfeng + 0 comments [deleted] - EB
eabonelli + 1 comment It does reduce. It has a nested occurrence of Curry's combinator. Here is the result:

(λg.((λf.(f ((λx.(f (x x)))(λx.(f (x x)))) ((λx.(f (x x)))(λx.(f (x x))))) g)))

The reductions#3 exercise was also bugged. Please have someone with a lambda calculus background revise all the lambda calculus exercises

_hdtx_ + 0 comments The exercise requires you to reduce to "one term" (which here means a single variable name), or the result string must be "can't reduce". It does not mean you can't apply any reductions. Slightly confusing, I know.

No more comments

Sort 3 Discussions, By:

Please Login in order to post a comment