仅使用增量，循环，赋值，零的减法运算 [英] Subtraction operation using only increment, loop, assign, zero

问题描述

我正尝试仅使用以下操作来建立减法，加法，除法，乘法和其他运算:

I am trying to build up subtraction, addition, division, multiplication and other operations using only following ones:

1. incr(x)-调用此函数后，会将x +1分配给x
2. assign(x，y)-此函数会将y的值分配给x(x = y)
3. zero(x)-此函数会将0分配给x(x = 0)
4. 循环X {}-用括号括起来的操作将执行X次

使用以下规则，可以很容易地实现这样的加法(add):

Using following rules it is straight forward to implement addition (add) like this:

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

但是，我正在努力实现减法.我认为所有其他需要的操作都可以通过减法来完成.

However, I'm struggling to implement subtraction. I think that all the other needed operations could be completed using subtraction.

任何提示将不胜感激.

推荐答案

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

Stephen Cole Kleene devised a way to perform integer subtraction using integer addition. However, it assumes that you cannot have negative integers. For example:

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

在您的问题中，您使用增量运算实现了加法运算.

In your question, you implemented the addition operation using the increment operation.

类似地，您可以使用减量运算来实现减法运算，如下所示:

Similarly, you can implement the subtraction operation using the decrement operation as follows:

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

现在，我们要做的就是执行减量运算.

Now, all we need to do is implement the decrement operation.

这是Kleene的才华横溢的地方:

This is where the genuis of Kleene shines:

decr(x) {
    y = 0
    z = 0

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

    return y
}

在这里，我们已经使用了全部四个操作.它是这样工作的:

Here we've used all the four operations. This is how it works:

1. 我们有两个基本案例，y(0的基本案例)和z(1的基本案例):

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

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

Hence, we initialize them both to 0.

当x为0时，我们运行循环0次(即从不执行)，然后我们简单地返回y = 0.

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

当x为1时，我们运行一次循环，分配y = z，然后简单地返回y = z = 0.

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

请注意，每次运行循环时，y都会保存当前迭代的结果，而z会保存下一次迭代的结果.这就是为什么我们需要两个基本案例的原因.递减函数不是连续函数.这是一个逐项函数:

Notice that every time we run the loop y holds the result of the current iteration while z holds the result of the next iteration. This is the reason why we require two base cases. The decrement function is not a continuous function. It is a piecewise function:

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

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

Kleene realized this when he went to the dentist and the dentist extracted two of his teeth. He was frustrated while trying to solve this very problem and when the dentist extracted two of his teeth he realized that he required two base cases.

这篇关于仅使用增量，循环，赋值，零的减法运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！