0. Identify the free and bound variables in the following term Remenber: whether
ID: 3744715 • Letter: 0
Question
0. Identify the free and bound variables in the following term Remenber: whether a tern is free or bound is always relative to a given term. What are the free and bound variables for just the tern inside the 1. Determine if the following pairs of terms are alpha-equivalent a lambda x.lanbda y. (x y x) ano lambda x.lanbda y. ( x y) b. lambda x lambda y. x (lanbda y.x) y and lambda a lambda b. a (lanbda u.a) b For the rest of the problens, find the beta-normal forns of the following ters Renember: you can renane bound variables to avoid possible clash, but never free variables. Also, application associates to the left: abcis the same as (a b) c, but not the sane as a (b c 2. (lambda .1ambda y. (y x)) u (1arbda x.x) 3. given S, K, I as they are in the handout, find the noral forms of KII, SIK, SK(KI), and S(KI). Application associates to the left and the order is inportant T lanbda f.lanbda x.f (x) find the nornal form of (AT T) Conjecture what would happen if T- lambda f.labda x.f (f (f )) T is the "Church representation" of the number 2, and A represents Addition Church originally fornulated the lanbda calculus as a synbolic foundation for all of mathematics 4b (NEN OPTIONAL CHALLENGE) Church exponentiation, n to the nth power, is lanbda n. 1ambda n.(n n) Show that 2 to 3rd power 8 using the Church representation 5. Given T anbda x. lambda y. x F lanbda x. lambda y. y D- 1ambda p.lanbda q. ( q) (where T is as above) Find the normal forms of: a- (DF F) b. (DFT) C. (D T F) d. (D T T) Does anything about the behavior of tese lambda terms look faniliar? (pretend you're all excited now and want to know more!) 6. Let T and F be as they were in the above problem, and let N- lambda x. (x F T) what are the normal forns of a.(NF) b. (N T) C (N (N T))Explanation / Answer
Understand the basic terminologies used in this questions:
Free variables: The non-local variables
Alpha equivalent: which is often referred as alpha conversion states that if the binding variable in lambda can be changed which will not affect the meaning of the expression.
0: lambda u. lambda x. [x (lambda y.x y) u y] the bolded y is the only free variable.
the other y in (lambda y.x y) is bound by the lambda y.
1: a) is not an alpha-equivalent.
b): is an alpha equivalent since the inner lambda y can be converted into lambda u
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.