Sort 5 Discussions, By:
Please Login in order to post a comment
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.
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).
c = (λf.(b b))
b = (λx.(f (x x)))
We clearly can replace f with g here, so we have
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.
Agreed, it doesn't make sense to waste an interesting challenge and make it trivial! The original question doesn't even need thinking as you mentioned! The outer Abstraction is not Applied to anything, so how can one reduce it to a single term?
(λ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
I think that it is kind of missleading to put in CAN'T REDUCE in quotes in the question body. I tried to submit it like that and it failed. Perhaps they should change it so it is more clear.
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?
It's related to the "omega function" solution to the previous problem.
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
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