【四进制造物主】小说免费阅读,请收藏 一七小说【1qxs.com】
add=ρ^1(proj11,succ·[proj33])
完美无瑕。
类似地,乘法器mult=ρ^1(zero,add·[proj13,proj33])
前继函数,减法器等等基本运算都可以据此定义,只需要proj,zero,succ三种原始函数和组合·,原始递归ρ这两种基本操作。所有完全函数都可以据此构造。
那么“偏函数”呢?
构造偏函数还需要额外的一个操作:最小化。
如果我们有一个函数f:N^n+1—N (这里^代表上标,虽然不好看,但实在是敲得太麻烦没有耐心了),具体的f(a1,...an,x),其中a1,...an是固定参数,x是可变参数。
那么最小化操作为:μ^nf:N^n—N它会找到给它输入的n个参数里,最小的一个,并输出
比如f(5,4,3,2,1,0)=0
如果遇到重复参数,那么就输出第一个最小的。
比如f(5,4,3,2,1,1)=1
假设我们有一个投影函数长这样:
proj21:N^2—N (proj21中的2是上标,1是下标,下同,写不动摆烂了)
那么μ^1proj21:N—N
举个栗子:
假如我们给proj21弄一个最小化操作:μ^1proj21(1),其中1是固定参数。
如果我们穷举一下可变参数,就会发现:
proj21(1,0)=1
proj21(1,1)=1
我们永远也拿不到0,也就不存在最小化。也就是说,对于μ^1proj21而言,并不是每一个输入都对应一个输出,所以应用最小化操作,我们成功地构建了一个偏函数。
加减乘三种操作都在上文构建过了,现在就只剩下一个除了。除法div需要用最小化操作来构建。
假设,我们收到两参数a和b,想求a/b,那么其中存在如下关系:
a=q×b+r,其中0≤r<b
我们想要的就是满足式子q×b≤a的最大的q,这等同于满足(q+1)×b>a,于是带余除法被转化为了一个最小化问题:
找到最小的q使其满足(q+1)×b>a
也就是构造一个函数f:N^3—N
f(a,b,q)=1如果(q+1)b≤a,=0如果(q+1)b>a
f(a,b,q)=lessthanequal(mult(succ(q),b),a)
f=lessthaneual·[mult·[succ·[proj33],proj32],proj31]
其中lessthanequal=iszero·sub
本章未完,点击[下一页]继续阅读-->