部分递归函数
书籍:逻辑百科辞典
由初始函数(参见原始递归函数)出发，经有穷次使用复合、原始递归和取极小三种运算而得到的函数。也称μ－递归函数。由于使用了取极小运算，所以会得到定义域不全的函数。如果部分递归函数f的定义域是全的，称之为递归全函数。在有些文献中，递归全函数等同于递归函数；在另一些文献中，部分递归函数等同于递归函数。本书采用后一种用法。原始递归函数都是递归全函数(因而是部分递归函数)，但反之不然。适当增加初始函数，也可以不用原始递归运算，只靠复合和取极小两种运算就能产生全体部分递归函数。例如取以下函数作初始函数：
S(x)(后继函数)，
(x，…，x)(1≤j≤n)，
x+y，
x－y，
xy．