只使用增量、循环、赋值和零实现减法操作

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）：

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

不过，我正在努力实现减法。 我认为可以使用减法完成所有其他所需的操作。

任何提示将不胜感激。

- fiz

---

你确定这是可能的吗？看起来你创建的任何新值都会是一个固定常数或者输入的正仿射函数。 - templatetypedef

可能是，我听到了这个问题。我自己没有看到过。但肯定没有像减量这样的函数。 - fiz

你可以使用负数吗？ - Aadit M Shah

@AaditMShah 不可以，这是不被允许的。 - fiz

@templatetypedef 确实是可能的。请看下面的回答。 - Aadit M Shah

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. We have two base cases, y (the base case for 0) and z (the base case for 1):

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

   Hence, we initialize them both to 0.

2. When x is 0 we run the loop 0 times (i.e. never) and then we simply return y = 0.

3. When x is 1 then we run the loop once, assign y = z and then simply return y = z = 0.

注意每次运行循环时，y保存当前迭代的结果，而z保存下一次迭代的结果。这就是为什么我们需要两个基本情况的原因。减量函数不是连续函数。它是一个分段函数：

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

Kleene意识到这一点是当他去看牙医拔了两颗牙齿时。他在尝试解决这个问题的过程中感到沮丧，但当牙医拔掉他的两颗牙齿时，他意识到他需要两个基本情况。

- Aadit M Shah

---

这是一个很好的解释！您能否说明如何仅使用给定的操作检查两个变量的相等性？- @Aadit M Shah - korujzade

@koruj 当然可以。如果您将其发布为问题，我会为您提供答案。 - Aadit M Shah

@korujzade 我在这里回答了你的问题：https://dev59.com/b5Pea4cB1Zd3GeqP-heJ?lq=1 - Aadit M Shah