仅使用增量、循环、赋值、零的减法运算

Question

我正在尝试仅使用以下运算来构建减法、加法、除法、乘法和其他运算：

1. incr(x) - 一旦调用此函数，它将 x + 1 分配给 x
2. assign(x, y) - 此函数将把 y 的值赋给 x (x = y)
3. zero(x) - 此函数会将 0 分配给 x (x = 0)
4. loop X { } - 括号内的操作将执行 X 次

使用以下规则可以直接实现加法（添加），如下所示：

ADD (x, y) {
 loop X {
   y = incr (y)
 }
return y
}

但是，我正在努力实施 减法。我认为所有其他需要的操作都可以使用减法来完成。

任何提示将不胜感激。

Answer 1

Stephen Cole Kleene 设计了一种使用整数加法执行整数减法的方法。但是，它假设您不能有负整数。例如：

0 - 1 = 0
1 - 1 = 0
2 - 1 = 1
3 - 1 = 2
4 - 1 = 3
5 - 2 = 3
6 - 3 = 3
6 - 4 = 2
6 - 5 = 1
6 - 6 = 0
6 - 7 = 0

在你的问题中，你使用增量操作实现了加法操作。

同理，可以使用减操作来实现减操作，如下：

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

现在，我们需要做的就是实现自减操作。

这就是 Kleene 天才的闪光点：

decr(x) {
    y = 0
    z = 0

    loop x {
        y = z
        z = incr(z)
    }

    return y
}

这里我们使用了所有四个操作。它是这样工作的：

1. 我们有两个基本情况，y（0 的基本情况）和 z（1 的基本情况）：

   y = 0 - 1 = 0
   z = 1 - 1 = 0
   

   因此，我们将它们都初始化为0。

2. 当 x 是 0 时，我们 运行 循环 0 次（即从不）然后我们简单地 return y = 0.

3. 当x是1那么我们运行循环一次，分配y = z然后简单地returny = z = 0.

请注意，每次我们 运行 时，循环 y 保存当前迭代的结果，而 z 保存下一次迭代的结果。这就是我们需要两个基本案例的原因。减量函数不是连续函数。这是一个 piecewise 函数：

decr(0)     = 0
decr(n + 1) = n

Kleene 在去看牙医时意识到了这一点，牙医拔掉了他的两颗牙齿。在试图解决这个问题时，他感到很沮丧，当牙医拔掉他的两颗牙齿时，他意识到他需要两个基本案例。