Question

In: Computer Science

Given, op: (λ(n) (λ(f) (λ(x) (((n (λ(g) (λ(h) (h (g f))))) (λ(u) x)) (λ(u) u))))) zero:...

Given, op: (λ(n) (λ(f) (λ(x) (((n (λ(g) (λ(h) (h (g f))))) (λ(u) x)) (λ(u) u)))))

zero: (λ(f) (λ(x) x))

one: (λ(f) (λ(x) (f x)))

two: (λ(f) (λ(x) (f (f x))))

three: (λ(f) (λ(x) (f (f (f x)))))

i. (4 pt) What is the result of (op one)?

ii. (4 pt) What is the result of (op two)?

iii. (4 pt)What is the result of (op three)?

iv. (3 pt) What computation does op perform?

Expert Solution

Understand Before proceed further:

One way of thinking about the Church numeral n, which is often useful when analysing programs, is as an instruction 'repeat n times'. For example, using the PAIR and NIL functions defined below, one can define a function that constructs a (linked) list of n elements all equal to x by repeating 'prepend another x element' n times, starting from an empty list. The lambda term is

λn.λx.n (PAIR x) NIL

By varying what is being repeated, and varying what argument that function being repeated is applied to, a great many different effects can be achieved.

Solution op(i)

Given (λ(f) (λ(x) (f x)))

Because the m-th composition of f composed with the n-th composition of f gives the m+n-th composition of f, addition can be defined as follows:

λm.λn.λf.λx.m f (n f x)

Solution op(ii)

Given (λ(f) (λ(x) (f (f x))))

Again m-th composition of f composed with the n-th composition of f gives the m+n-th composition of f.

λm.λn.λf.λx.m f(f (n f x))

Solution op(iii)

Given (λ(f) (λ(x) (f (f (f x)))))

Here also λm.λn.λf.λx.m f(f (f(n f x)))

Solution op(iv)

op : λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)

By convention, the following operation (known as Church booleans) are used for the boolean values TRUE and FALSE:

TRUE := λx.λy.x

FALSE := λx.λy.y

(Note that FALSE is equivalent to the Church numeral zero defined above).

Then, with these two lambda terms, we can define some logic operators (these are just possible formulations; other expressions are equally correct):

AND := λp.λq.p q p

OR := λp.λq.p p q

NOT := λp.p FALSE TRUE

IFTHENELSE := λp.λa.λb.p a b

We are now able to compute some logic functions, for example:

AND TRUE FALSE

≡ (λp.λq.p q p) TRUE FALSE → TRUE FALSE TRUE

≡ (λx.λy.x) FALSE TRUE → FALSE

venereology answered 2 years ago

if f and g are the functions whose graphs are shown, let u(x) = f(x)g(x) and v(x) = f(x)/g(x).

if f and g are the functions whose graphs are shown, let u(x) = f(x)g(x) and v(x) = f(x)/g(x) (a) Find u'(1) (b) Find v'(5).

For countable set G, H = {f : N → G : f is injective} where...

For countable set G, H = {f : N → G : f is injective} where N is the natural numbers. What is the cardinality of H. Prove it.

find zero state response y[n+4]-y[n]=x[n], if x[n]= e^-n u[n]

(abstract algebra) Let F be a field. Suppose f(x), g(x), h(x) ∈ F[x]. Show that the...

(abstract algebra) Let F be a field. Suppose f(x), g(x), h(x) ∈ F[x]. Show that the following properties hold: (a) If g(x)|f(x) and h(x)|g(x), then h(x)|f(x). (b) If g(x)|f(x), then g(x)h(x)|f(x)h(x). (c) If h(x)|f(x) and h(x)|g(x), then h(x)|f(x) ± g(x). (d) If g(x)|f(x) and f(x)|g(x), then f(x) = kg(x) for some k ∈ F \ {0}

Let f(x) = (x − 1)2, g(x) = e−2x, and h(x) = 1 + ln(1 − 2x). (a) Find the linearizations of f, g, and h at a =...

Let f(x) = (x − 1)2, g(x) = e−2x, and h(x) = 1 + ln(1 − 2x). (a) Find the linearizations of f, g, and h at a = 0. Lf (x) = Lg(x) = Lh(x) = (b) Graph f, g, and h and their linear approximations. For which function is the linear approximation best? For which is it worst? Explain. The linear approximation appears to be the best for the function ? f g h since it is closer to ? f g h for a larger domain than it is to - Select - f and g g and h f and h . The approximation looks worst for ? f g h since ? f g h moves away from L faster...

Given that h(x)=x+3 and g(x)=sqrt of x-4, find (g+h)(4), if it exists.

1.)Prove that f(n) = O(g(n)), given: F(n) = 2n + 10; g(n) = n 2.)Show that...

1.)Prove that f(n) = O(g(n)), given: F(n) = 2n + 10; g(n) = n 2.)Show that 5n2 – 15n + 100 is Θ(n2 ) 3.)Is 5n2 O(n)?

1. For the function f(x)=x2−36 evaluate f(x+h). f(x+h)= 2. Let f(x)=3x+4,g(x)=9x+12, and h(x)= 9x^2+ 24x+16. evaluate...

1. For the function f(x)=x2−36 evaluate f(x+h). f(x+h)= 2. Let f(x)=3x+4,g(x)=9x+12, and h(x)= 9x^2+ 24x+16. evaluate the following: a. (fg)(3)= b. (f/g) (2)= c. (f/g) (0)= d.(fh)(-1)= 3. Let f(x)=2x-1, g(x)=x-3, and h(x) =2x^2-7x+3. write a formula for each of the following functions and then simplify a. (fh) (x)= b. (h/f) (x)= c. (h/g) (x)= 4.Let f(x)=5−x and g(x)=x^3+3 find: a. (f∘g)(0)= b.(g∘f)(0)= c. (f∘g)(x)= d. (g∘f)(x)= 5. Let f(x)=x^2+5x and g(x)=4x+5 find: a. (f∘g)(x)= b. (g∘f)(x)= c. (f∘g)(0)= d....

If f and g are both differentiable functions. If h = f g, then h'(2) is: ___________________

If f and g are both differentiable functions. If h = f g, then h'(2) is: ___________________ Given the function: y=sin(4x)+e^-3x and dx/dt = 3 when x=0. Then dy/dt = ________________ when x=0. Let f(x) = ln (√x). The value of c in the interval (1,e) for which f(x) satisfies the Mean Value Theorem (i.e f'(c)= f(e)-f(1) / e-1 ) is: _________________________ Suppose f(x) is a piecewise function: f(x) = 3x^2 -11x-4, if x ≤ 4 and f(x) =...

F(x)=g(x)*h(x) = 4x3-2x2+3x-1 solution