Relational operations using only increment, loop, assignment, zero

Question

This is the next question for: subtraction operations using only increment, loop, assign, zero

We are allowed to use only the following operations:

• incr (x) - as soon as this function is called, it will assign x + 1 to x
• assign (x, y) - this function assigns the value yx (x = y)
• zero (x) - this function assigns 0 x (x = 0)
• loop X {} - operations written in brackets will be executed X times

For example, an add-on can be implemented as follows:

add(x, y) { loop x { y = incr(y) } return y } 

How to implement relational operators using these four operations? Relational operations are:

• eq (x, y) - Is x equal to y?
• lt (x, y) - less than x than y?
• gt (x, y) - greater than x greater than y?

We also have their opposites:

• ne (x, y) - Is x not equal to y?
• gte (x, y) - is x greater than or equal to y?
• lte (x, y) - x is less than or equal to y?

Any help would be appreciated.

Answer 1

The set of natural numbers N closed with respect to addition and subtraction:

 N + N = N N - N = N 

This means that the addition or subtraction of two natural numbers is also a natural number (given 0 - 1 is 0 , not -1 , we cannot have negative natural numbers).

However, the set of natural numbers N does not close during relational operations:

 N < N = {0, 1} N > N = {0, 1} 

This means that the result of comparing two natural numbers is either truthfulness (i.e. 1 ) or false (i.e. 0 ).

So, we consider the set of Boolean elements (ie {0, 1} ) as a limited set of natural numbers (ie N ).

 false = 0 true = incr(false) 

The first question we need to answer is "how do we code if expressions so that we can branch out based on truthfulness or falsehood?" The answer is simple, we use the loop operation:

 isZero(x) { y = true loop x { y = false } return y } 

If the loop condition is true (i.e. 1 ), the loop executes exactly once. If the loop condition is false (i.e. 0 ), then the loop is not executed. We can use this to write branch code.

So how do we define relational operations? It turns out that everything can be defined in terms of lte :

 lte(x, y) { z = sub(x, y) z = isZero(z) return z } 

We know that x ≥ y coincides with y ≤ x . Therefore:

 gte(x, y) { z = lte(y, x) return z } 

We know that if x > y true, then x ≤ y is false. Therefore:

 gt(x, y) { z = lte(x, y) z = not(z) return z } 

We know that x < y same as y > x . Therefore:

 lt(x, y) { z = gt(y, x) return z } 

We know that if x ≤ y and y ≤ x , then x = y . Therefore:

 eq(x, y) { l = lte(x, y) r = lte(y, x) z = and(l, r) return z } 

Finally, we know that if x = y true, then x ≠ y is false. Therefore:

 ne(x, y) { z = eq(x, y) z = not(z) return z } 

Now all we need to do is define the following functions:

• The sub function is defined as follows:

   sub(x, y) { loop y { x = decr(x) } return x } decr(x) { y = 0 z = 0 loop x { y = z z = incr(z) } return y } 

• The not function is the same as the isZero function:

   not(x) { y = isZero(x) return y } 

• The and function is the same as the mul function:

   and(x, y) { z = mul(x, y) return z } mul(x, y) { z = 0 loop x { z = add(y, z) } return z } add(x, y) { loop x { y = incr(y) } return y } 

That is all you need. Hope this helps.