Some error occured while loading page for you. Please try again.
Sort 3 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.
(λ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 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