Question: Problem 5 [ 16pt] In the lecture, we have used the pure -calculus to construct natural numbers and encoded some operations on them. In such
Problem 5 [ 16pt] In the lecture, we have used the pure -calculus to construct natural numbers and encoded some operations on them. In such encoding, a number n is encoded as a function Af . fn z (denoted as n). In this problem, we wll define more useful operations on numbers. If you get stuck in any question try to procced by assuming the previous function is properly defined. You can reuse any encoding given in lectures and previous questions. a) (4pt) Define a function ISZERO in -calculus, so that given a number n, t returns TRUE (the encoding of true) if n = 0; FALSE (the encoding of false) if n0. Hint: try to define two terms so that applying the second term multiple times to the first term returns FALSE; otherwise, the application returns TRUE. b) (4pt) Define a function PRED in -calculus, so that given a number n, the function returns its predecessor. assuming the predecessor of 0 is Hint: follow the idea in Problem 4a. You might need to use PAIR. c) (4pt) Use your encoding of PRED to define a subtraction function MINUS, so that MINUS n1 n returns n1n when n1> no, and 0 otherwise d) (4pt) Based on what you have encoded so far, and the Boolean encodings in the lecture, define an equality test, called EQUALS on two numbers, so that it returns TRUE when two numbers are equal, and FALSE otherwise
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
