# Lambda Calculus - Reductions #4

# Lambda Calculus - Reductions #4

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

xdavidliu + 0 comments Note this problem trivially cannot be reduced to a "single term" since it the whole thing is a function, not a function

*application*. The problem should probably be changed from(λg.((λf.((λx.(f (x x)))(λx.(f (x x))))) g))

to something like

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

in order to actually be interesting. But let's look at the original anyway.

We can unroll the expression into a neater form: (Note I'm using the symbol "=" loosely here, but it is pretty unambiguous what I mean).

(λg.(c g)) c = (λf.(b b)) b = (λx.(f (x x)))

We clearly can replace f with g here, so we have

(λg.(b b)) b = (λx.(g (x x)))

This certainly cannot be reduced; if we try to evaluate (b b), we obtain

(g (b b)) (g (g (b b))) (g (g (g (b b)))) ...

and so on.

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

irenelfeng + 0 comments [deleted]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 4 Discussions, By:

Please Login in order to post a comment