第1章 上一章注释[001](3 / 4)

投票推荐 加入书签 留言反馈

  add=p1(proj11,succ·[proj33])
  完美无瑕。
  类似地,乘法器mult=p1(zero,add·[proj13,proj33])
  前继函数,减法器等等基本运算都可以据此定义,只需要proj,zero,succ三种原始函数和组合·,原始递归p这两种基本操作。所有完全函数都可以据此构造。
  那么“偏函数”呢?
  构造偏函数还需要额外的一个操作:最小化。
  如果我们有一个函数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:N2—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=qxb+r,其中0≤r<b
  我们想要的就是满足式子qxb≤a的最大的q,这等同于满足(q+1)xb>a,于是带余除法被转化为了一个最小化问题:
  找到最小的q使其满足(q+1)xb>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 ↑返回顶部↑

章节目录