Реляционные операции, использующие только приращение, цикл, присваивание, нуль

Множество натуральных чисел N замкнуто относительно сложения и вычитания:

N + N = N
N - N = N

Это означает, что сложение или вычитание двух натуральных чисел также является натуральным числом (учитывая, что 0 - 1 равно 0, а не -1, у нас не может быть отрицательных натуральных чисел).

Однако множество натуральных чисел N не замыкается относительно реляционных операций:

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

Это означает, что результатом сравнения двух натуральных чисел является либо правдивость (т.е. 1), либо ложь (т.е. 0).

Итак, мы рассматриваем набор логических значений (т. е. {0, 1}) как ограниченный набор натуральных чисел (т. е. N).

false = 0
true  = incr(false)

Первый вопрос, на который мы должны ответить, заключается в том, как нам кодировать if утверждения, чтобы мы могли переходить на основе либо правдивости, либо ложности? Ответ прост, используем операцию loop:

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

Если условие цикла true (т.е. 1), то цикл выполняется ровно один раз. Если условие цикла равно false (т. е. 0), то цикл не выполняется. Мы можем использовать это для написания кода ветвления.

Итак, как мы определяем реляционные операции? Оказывается, все можно определить с помощью lte:

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

Мы знаем, что x ≥ y совпадает с y ≤ x. Поэтому:

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

Мы знаем, что если x > y истинно, то x ≤ y ложно. Поэтому:

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

Мы знаем, что x < y совпадает с y > x. Поэтому:

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

Мы знаем, что если x ≤ y и y ≤ x, то x = y. Поэтому:

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

Наконец, мы знаем, что если x = y истинно, то x ≠ y ложно. Поэтому:

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

Теперь все, что нам нужно сделать, это определить следующие функции:

1. Функция sub определяется следующим образом:

   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. Функция not аналогична функции isZero:

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

3. Функция and аналогична функции mul:

   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
   }
   

Это все, что вам нужно. Надеюсь, это поможет.