递归函数（六）：最多有多少个程序
递归函数（一）：开篇
递归函数（二）：编写递归函数的思路和技巧
递归函数（三）：归纳原理
递归函数（四）：全函数与计算的可终止性
递归函数（五）：递归集与递归可枚举集
递归函数（六）：最多有多少个程序
递归函数（七）：不动点算子
递归函数（八）：偏序结构
递归函数（九）：最小不动点定理
- -
回顾
上一篇中，我们通过引入极小化算子定义了递归函数，
使用递归函数，我们又定义了递归集与递归可枚举集，
本文我们要讨论，为什么递归可枚举集是“可枚举”的，以及什么是可计算函数。
可计算性
我们听说过，现代计算机在计算能力上是与图灵机等价的，
什么叫做计算能力呢？
它指的是图灵机可计算的函数集，与现代计算机可计算的函数集是相等的。
为了简单起见，我们不去讨论图灵机，而是从现代计算机直接说起，
设\(mathscr{P}\)是一段程序，\(n\)是一个正整数，
我们称数论函数\(psi (x_1,x_2,cdots ,x_n)\)为程序\(mathscr{P}\)所计算的\(n\)元部分函数，
如果对于相同的输入，
要么：（1）程序\(mathscr{P}\)的计算可以终止，此时计算结果等于\(psi (x_1,x_2,cdots ,x_n)\)的相应函数值；
要么：（2）程序\(mathscr{P}\)的计算不能终止，此时\(psi (x_1,x_2,cdots ,x_n)\)无定义。
设\(f(x_1,x_2,cdots ,x_n)\)是一个部分函数，如果存在程序\(mathscr{P}\)可计算\(f\)，则称\(f\)是部分可计算的。
如果一个函数，既是部分可计算的，又是全函数，则称这个函数是可计算的。
可以证明，所有的原始递归函数和递归函数都是部分可计算的。
通用程序
我们使用现代计算机进行编程的时候，并不是直接把程序的输入传给程序，
而是将程序本身以及它的输入，传给计算机，最后由计算机得到计算结果，
像这种接受任何程序和它的输入作为自己的输入，返回程序执行结果的程序，称为通用程序。
为此，通用程序需要把输入的程序进行编码。
常用的编码方法，涉及配对函数和哥德尔编码。
为了不引入太多的复杂性，我们可以将程序的编码理解为存储程序的二进制数据，
不同的程序会有不同的二进制表示，每一个二进制表示可以对应一段程序（虽然可能不合法）。
哥德尔编码做的事情就是将程序和自然数集一一对应起来。
因此，所有程序的个数是可数的，而这些程序可计算的函数个数也一定是可数的，
它们可能是全函数，也可能是部分函数。
（其中，“可数”指的是可数集，可数集是与自然数集之间存在一一映射的集合。
然而，自然数集上的函数全体并不可数，（证略
所以肯定存在程序不可计算的函数。
集合个数的可枚举性
程序\(mathscr{P}\)所计算的函数，我们可以记为\(psi (x_1,x_2,cdots ,x_n)\)，
由此，我们可以定义通用程序\(Phi \)，则有，
\(Phi (x_1,x_2,cdots ,x_n,y)=psi (x_1,x_2,cdots ,x_n)\)
其中，\(y\)是程序\(mathscr{P}\)的编码。
因为，所有的程序与自然数集一一对应，
所以，\(Phi (x_1,x_2,cdots ,x_n,0),Phi (x_1,x_2,cdots ,x_n,1),cdots\)
枚举了所有的\(n\)元可计算函数。
我们定义\(W_y=lbrace xin N|Phi(x,y)downarrow rbrace \)，
根据递归可枚举集的定义，每一个\(W_y\)是一个递归可枚举集，
又因为\(Phi(x,0),Phi(x,1),cdots \)枚举了所有的可计算函数，
所以，\(W_0,W_1,cdots \)枚举了所有的递归可枚举集。
因此，集合\(B\)是递归可枚举的，当且仅当存在\(yin N\)，使得\(B=W_y\)，
称为枚举定理，这就是“枚举”的含义。
令\(K=lbrace nin N|nin W_nrbrace \)，
则\(K\)是递归可枚举的，但不是递归的，（证略
因此，\(bar{K}\)不是递归可枚举的，否则\(K\)就是递归集了。
（根据，集合\(B\)是递归的当且仅当\(B\)和\(bar{B}\)是递归可枚举的，见上一篇
因此，我们找到了一个非递归的递归可枚举集\(K\)，
以及一个非递归可枚举集\(bar{K}\)。
停机问题
任给一个程序和一个自然数，问该程序对这个自然数输入的计算是否停止，
这个问题称为停机问题。
我们可以用谓词\(H(x,y)\)描述这个问题，
\(H(x,y)\)，表示以\(y\)为代码的程序对输入\(x\)的计算最终停止。
那么，\(H(x,y)\)是不可计算的，即，不存在一个程序来计算\(H(x,y)\)。
我们来证明一下，假设有一个程序可以计算\(H(x,y)\)，
那么我们就能用它来构造一个新程序\(mathscr{P}\)，它的输入是\(x\)，
这段程序当\(H(x,x)\)为真时，计算不停止，而当\(H(x,x)\)为假时，计算停止。
程序\(mathscr{P}\)也可以进行编码，假设为\(y_0\)，现在我们来判断\(H(y_0,y_0)\)。
如果\(H(y_0,y_0)\)为真，意味着编码为\(y_0\)的程序以\(y_0\)作为输入最终停止，
即程序\(mathscr{P}\)，输入为\(y_0\)时，最终停止，
可是根据\(mathscr{P}\)的定义，此时\(H(x,x)=H(y_0,y_0)\)为假才会停止，矛盾。
如果\(H(y_0,y_0)\)为假，意味着编码为\(y_0\)的程序以\(y_0\)作为参数最终不会停止，
即程序\(mathscr{P}\)，输入为\(y_0\)时，最终不停止，
可是根据\(mathscr{P}\)的定义，此时\(H(x,x)=H(y_0,y_0)\)为真才不会停止，矛盾。
\(H(y_0,y_0)\)不能为真也不能为假，矛盾，
因此，计算\(H(x,x)\)的程序不存在，我们也无法用它来构造程序\(mathscr{P}\)。
可判定性
可判定性问题，指的是一个询问真或者假的问题是否可以被回答。
如果我们总能回答出这个问题是真或者是假，就称该问题是可判定的，
如果我们只能当问题为真的时候确定为真，为假的时候所进行的计算可能不会终止，那么就称该问题是半可判定的。
某元素是否属于一个递归集，是可判定的，
某元素是否属于一个递归可枚举集，是半可判定的。
因为，递归集使用一个递归的全函数定义的，
而递归可枚举集是使用第一个部分递归函数定义的，
我们无法判断某个部分递归函数，在接受某参数时，是没有定义，还是计算尚未停止。
即，判断元素是否属于某递归可枚举集的程序可能永不停机。
总结
本文介绍了函数的可计算性，通用程序，以及最多有多少个程序，
还了解了停机问题和可判定性问题。
这些都是可计算性理论的基础，我们清晰的看到了人类的计算能力，
以及用递归所能计算的函数范围，后文中我们开始讨论不动点理论，
这同样是一个有趣的话题。
- -
附
配对函数和哥德尔数，是对数偶和有穷数列的一种编码方式。
（1）配对函数
令\(langle x,yrangle=2^x(2y+1)-1\)，称\(langle x,yrangle \)为配对函数，它是一个原始递归函数。
任给一个数\(z\)，存在唯一的一对数\(x\)和\(y\)，使得\(langle x,yrangle =z\)。
\(x\)是\(z+1\)含有因子\(2\)的个数，即使得\(2^t|(z+1)\)的\(t\)的最大值。
\((z+1)/2^x\)必为奇数，\(y\)是\(2y+1=(z+1)/2^x\)的唯一解。
一般的，记\(l(z)=x\)，\(r(z)=y\)，则\(l(z)\)和\(r(z)\)也是原始递归函数。
（2）哥德尔数
记\([a_1,a_2,cdots ,a_n]=prod_{i=1}^{n}p_i^{a_i}\)，
\([a_1,a_2,cdots ,a_n]\)称为有穷数列\((a_1,a_2,cdots ,a_n)\)的哥德尔数。
其中，\(p_i\)是第\(i\)个素数。
例如，\([2,0,1,3]=2^2cdot 3^0cdot 5^1cdot 7^3=6860\)。
对于每一个固定的\(n\)，\([a_1,a_2,cdots ,a_n]\)是原始递归函数，并且这种编码具有唯一性。
- -