回顾
上文中我们讨论了全函数和部分函数，以及计算的可终止性。
本文我们从数论函数开始，给原始递归函数集增加一种新的运算，得到了一个更大的集合。
然后根据递归函数，我们可以定义递归集和递归可枚举集，
为以后讨论可计算性与可判定性打好基础。
数论函数
自然数集一般记为，那么个自然数集的笛卡尔积记为，
于是，我们称集合到的部分函数为元部分数论函数。
作为数论函数，是一个全函数，而，，只是部分函数，
它们的计算结果，，，都不在中，于是相应定义域中的点可视为没有定义。
为什么讨论数论函数呢，其一是因为它是一个典型数学的问题，
另外一点，则是因为我们经常把其他数学问题转换成数论问题，例如，哥德尔编码。
本文中，使用数论函数，可以简化我们的描述方式。
一个谓词，指的是返回布尔值的函数，
我们还可以将谓词看做值域为的一个数论函数。
代表True，代表False。
极小化算子
在前一篇中，我们从三个初始函数出发，
通过合成运算和原始递归运算，得到了原始递归函数集，
递归函数集是相对于这两种运算封闭的。
然而，这样定义的原始递归函数，并不能包括所有的数论函数，
一个典型的例子就是，阿克曼函数，
1 | ackermann :: Int -> Int -> Int |
它并不是一个原始递归函数，（证略
因此原始递归函数集并不足以表示计算机程序中的所有函数。
为此，我们需要对原始递归函数集进行扩充，我们定义一个新的运算，称为极小化运算，
设是一个谓词，令
的值，或者是使为真的最小值，
或者无定义，此时不存在使得为真。
这样通过得到的过程称为极小化运算，
也称部分函数是由谓词经过极小化运算得到的。
以上我们给谓词定义了极小化运算，现在我们将极小化运算推广到一般的函数上面，
设是一个元函数，令
则称部分函数是由函数经过极小化运算得到的。
递归函数集
和定义原始递归函数集一样，我们从以下三个初始函数出发，
（1）零函数
（2）后继函数
（3）投影函数，
由初始函数，经过有限次合成运算，原始递归运算，以及极小化运算，得到的函数称为递归函数。
递归函数并不一定是全函数，因为极小化运算可能会导致结果函数在某些点无定义，
递归的部分函数称为部分递归函数。
可以证明阿克曼函数是递归函数，但不是原始递归函数，
因此，原始递归函数集是递归函数集的真子集。
递归可枚举集
在具体实践中，我们经常会遇到这样的问题，
给定一个元素，我们需要判断这个元素是否属于某个集合。
这种问题，称为集合的成员资格问题。
沿用这一思路，我们可以使用一个谓词来定义相应的集合，
谓词为真，则。
这个谓词，通常称为集合的特征函数。
如果特征函数是一个递归的全函数，
则我们总是可以判断等于还是，
这样的集合称为递归集。
如果存在部分递归函数，使得，
即，当且仅当在处有定义，
则称集合是一个递归可枚举集。
每一个部分递归函数，都确定出一个递归可枚举集。
因此，对于每一个自然数，
我们总是可以通过递归集的特征函数，来判断是否的成员。
而对于递归可枚举集，就不容乐观了，
如果某个自然数是的成员，那么我们可以断定这件事，因为有定义，
但是如果某个自然数不是的成员，我们就不能确定，因为这时候无定义。
（无定义，则它对应的图灵机不停机，后文我们详细讨论
因此，集合是递归的当且仅当和是递归可枚举的，
其中为的补集。
总结
本文介绍了数论函数，递归函数集，然后用递归函数分别定义了递归集和递归可枚举集，
可是为什么递归可枚举集是“可枚举”的呢？
是因为每一个递归可枚举集可以一一对应一个自然数，这是怎样做到的呢？
这需要我们理解总共有多少个可能的程序，以及什么是通用程序。