第1章 上一章注释［001］(第4/5 页)

，并不是每一个输入都对应一个输出，所以应用最小化操作，我们成功地构建了一个偏函数。

加减乘三种操作都在上文构建过了，现在就只剩下一个除了。除法div需要用最小化操作来构建。

假设，我们收到两参数a和b，想求a\/b，那么其中存在如下关系：

a=qxb+r，其中0≤r＜b

我们想要的就是满足式子qxb≤a的最大的q，这等同于满足q+1xb＞a，于是带余除法被转化为了一个最小化问题：

找到最小的q使其满足q+1xb＞a

也就是构造一个函数f:N^3—N

fa，b，q=1如果q+1b≤a，=0如果q+1b＞a

fa，b，q=lessthanequalmultsuccq，b，a

f=lessthaneual·[mult·[succ·[proj33]，proj32]，proj31]

其中lessthanequal=iszero·sub

iszero=sub·[succ·zero，proj11]

sub是减法器

对f进行最小化操作即可得到我们想要的结果。

验证一下：

f8，5，0=lessthanequalmult1，5，8=1不等于0，所以0不是输出。

f8，5，1=lessthanequalmult1，5，8=0，最小，所以1是输出。

div8，5=8\/\/5=1没错，十分完美。

如果我们想计算一下8\/\/0:

f8，0，0=lessthanequalmult1，0，8=1不等于0，所以0不是输出。

f8，0，1=lessthanequalmult2，0，8=1不等于0，所以0不是输出。

无论我们给f8，0，x传入什么x，都找不到最小的x，所以div8，0=8\/\/0无解，符合现实。

如果把最小化操作运用在原始递归函数上，得到的新函数就叫做偏递归函数。

好了，现在加减乘除我们都有了，只要是可计算的算法，我们都能执行。

至于无限循环怎么制造出来，从μ^1proj211和div的栗子都可以看出来，如果最小化操作找不到最小值，就永远不会给出输出