We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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(xx)))(λx.(f(xx)))))g))
to something like
((λg.((λf.((λx.(f(xx)))(λx.(f(xx)))))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.(cg))c=(λf.(bb))b=(λx.(f(xx)))
We clearly can replace f with g here, so we have
(λg.(bb))b=(λx.(g(xx)))
This certainly cannot be reduced; if we try to evaluate (b b), we obtain
(g(bb))(g(g(bb)))(g(g(g(bb))))...
and so on.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lambda Calculus - Reductions #4
You are viewing a single comment's thread. Return to all 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
to something like
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).
We clearly can replace f with g here, so we have
This certainly cannot be reduced; if we try to evaluate (b b), we obtain
and so on.