algorithm - Relational operations using only increment, loop, assign, zero -

this follow question for: subtraction operation using increment, loop, assign, zero

we're allowed use following operations:

1. incr(x) - once function called assign x + 1 x
2. assign(x, y) - function assign value of y x (x = y)
3. zero(x) - function assign 0 x (x = 0)
4. loop x { } - operations written within brackets executed x times

for example, addition can implemented follows:

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

how implement relational operators using these 4 operations? relational operations are:

1. eq(x, y) - x equal y?
2. lt(x, y) - x lesser y?
3. gt(x, y) - x greater y?

we have opposites:

1. ne(x, y) - x not equal y?
2. gte(x, y) - x greater or equal y?
3. lte(x, y) - x lesser or equal y?

any appreciated.

the set of natural numbers n closed under addition , subtraction:

n + n = n n - n = n 

this means addition or subtraction of 2 natural numbers natural number (considering 0 - 1 0 , not -1, can't have negative natural numbers).

however, set of natural numbers n not closed under relational operations:

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

this means result of comparing 2 natural numbers either truthfulness (i.e. 1) or falsehood (i.e. 0).

so, treat set of booleans (i.e. {0, 1}) restricted set of natural numbers (i.e. n).

false = 0 true  = incr(false) 

the first question must answer “how encode if statements may branch based on either truthfulness or falsehood?” answer simple, use loop operation:

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

if loop condition true (i.e. 1) loop executes once. if loop condition false (i.e. 0) loop doesn't execute. can use write branching code.

so, how define relational operations? turns out, can defined in terms of lte:

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

we know x ≥ y same y ≤ x. therefore:

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

we know if x > y true x ≤ y false. therefore:

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

we know x < y same y > x. therefore:

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

we know if x ≤ y , y ≤ x x = y. therefore:

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

finally, know if x = y true x ≠ y false. therefore:

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

now, need define following functions:

1. the sub function defined 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 } 

2. the not function same iszero function:

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

3. the and function same 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's need. hope helps.