How to define arithmetic operations using church numerals

Reference no: EM132325337

Assignment

1. Different notions of normal form have been discussed in the literature, including the full normal form (or simply normal form) and weak head normal form.

a. What is the difference between a term having a normal form and being a normal form? Write down some example terms.

A term has a normal form when there are still redexes possbile through reduction. A term such as λabc.(( λx.a(λy.xy))b c ) for example can still be normalized.

When a term is in normal form, that means thare are no redexes left for it. Going with the example I mentioned above, λabc.(a(λy.by)c) for example, would be in normal form since there are no further redexes left for the term.

b. If a closed term is a weak head normal form, it has to be an abstraction "λx.M". Why?

c. Indicate whether the following λ-terms have a normal form:

-- (λx.(λy.yx)z)v

-- (λx.xxy)(λx.xxy)

d. Show that the term Ω = (λx.xx)(λx.xx) does not have a normal form. Find a term different from Ω that is not normalizing (i.e., a term such that every reduction sequence starting from it is infinite).

2. It has been shown how to define arithmetic operations using Church numerals.

a. Check that the term ADD = λxyab.(xa)(yab) behaves like the addition function; that is, show that when we apply ADD to two Church numerals, the Church numeral representing their sum is obtained. Hint: Reduce the term (λx.λy.λa.λb.(xa)(yab)nm.

b. Show that the λ-term MULT = λx.λy.λz.x(yz) applied to two Church numerals m and n computes their product m x n.

c. Which arithmetic operation does the term λn.λm.m (MULT n)1 compute?

3. Compute the normal forms of the following terms (Where I = λx.x and K = λxy.x):

a. λy.(λx.x)y

b. λy.y(λx.x)

c. II

d. KI

e. KKK

Reference no: EM132325337

Questions Cloud

Discuss the leadership and management strengths : Assignment 1: Contemporary Educational Management. Discuss the leadership and management strengths of your Principal or HOD or Manager

Evaluate and describe your personal learning style : BSBLED503-Maintain and enhance professional practice-Victoria University-Australia-Evaluate the skills you have that match the organisation’s goals.

What is responsible for experts superior performance : Are experts better at solving problems than non-experts? If so, what is responsible for experts' superior performance? Is their superiority general or limited.

What are the characteristics of communication : Purpose of this paper is to articulate your development as a leader from a Christian worldview. Paper must be 2,500-2,700 words and be APA formatted.

How to define arithmetic operations using church numerals : Different notions of normal form have been discussed in the literature, including the full normal form (or simply normal form) and weak head normal form.

What steps you can take to overcome challenges : Elaborate on specific areas that you anticipate to be a challenge in developing a portfolio and what steps you can take to overcome those challenges.

How specifics will be applied in your degree : You have covered a lot in these past eight weeks. Your new-found ability to impact others through coaching is now a tangible tool you can use.

How government insurers impact actual reimbursement : Write a 750-1,000 word synopsis describing the different types of payment that are taken for health care. Describe how private and government insurers.

Define a problem on the dataset : CISC520 Data Engineering and Mining-Harrisburg University of Science & Technology-US-Define a problem on the dataset and describe it.

User Account

All Pages