This is a follow up question for: Subtraction operation using only increment, loop, assign, zero
We're only allowed to use the following operations:
- incr(x) - Once this function is called it will assign x + 1 to x
- assign(x, y) - This function will assign the value of y to x (x = y)
- zero(x) - This function will assign 0 to x (x = 0)
- loop X { } - operations written within brackets will be executed X times
For example, addition can be implemented as follows:
add(x, y) {
loop x
{ y = incr(y) }
return y
}
How do I implement the relational operators using these four operations? The relational operations are:
- eq(x, y) - Is x equal to y?
- lt(x, y) - Is x lesser than y?
- gt(x, y) - Is 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) - Is x lesser than or equal to y?
Any help will be appreciated.
The set of natural numbers
N
is closed under addition and subtraction:This means that the addition or subtraction of two natural numbers is also a natural number (considering
0 - 1
is0
and not-1
, we can't have negative natural numbers).However, the set of natural numbers
N
is not closed under relational operations:This means that the result of comparing two natural numbers is either truthfulness (i.e.
1
) or falsehood (i.e.0
).So, we treat the set of booleans (i.e.
{0, 1}
) as a restricted set of the natural numbers (i.e.N
).The first question we must answer is “how do we encode
if
statements so that we may branch based on either truthfulness or falsehood?” The answer is simple, we use theloop
operation:If the loop condition is
true
(i.e.1
) then the loop executes exactly once. If the loop condition isfalse
(i.e.0
) then the loop doesn't execute. We can use this to write branching code.So, how do we define the relational operations? Turns out, everything can be defined in terms of
lte
:We know that
x ≥ y
is the same asy ≤ x
. Therefore:We know that if
x > y
is true thenx ≤ y
is false. Therefore:We know that
x < y
is the same asy > x
. Therefore:We know that if
x ≤ y
andy ≤ x
thenx = y
. Therefore:Finally, we know that if
x = y
is true thenx ≠ y
is false. Therefore:Now, all we need to do is define the following functions:
The
sub
function is defined as follows:The
not
function is the same as theisZero
function:The
and
function is the same as themul
function:That's all you need. Hope that helps.