仅使用递增,循环,赋值,零的减法运算

Question

我正在尝试使用以下方法建立减法,加法,除法,乘法和其他操作:

1. incr(x) - 一旦调用此函数,它将x + 1分配给x
2. assign(x,y) - 此函数将y的值赋给x(x = y)
3. 零(x) - 此函数将0分配给x(x = 0)
4. 循环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的genuis闪耀的地方:

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时间(即从来没有),然后我们就返回y = 0.

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

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

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

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