程序编号与可接受编号

通用图灵机理路通用图灵机Universal Turing machine输入机器编码和输入串后模拟该机器运行的图灵机。说明程序能够作为数据交给一个固定解释器。可接受编号再要求这套代码系统不仅能解释，还能有效地把参数写进程序，像编译器把“程序模板 + 常量”变成新程序。自指和递归定理依赖的是这种可操作的代码结构，而不是把源码任意贴上整数标签。

索引描述语法，${\phi }_e$ 描述行为。许多不同程序会计算同一个偏函数；程序优化、无用指令和不同实现都可改变索引而保持语义。因此比较索引数值与比较程序行为，是两个不同的问题。

把每台图灵机的有限转移表编码为自然数，并令 ${\phi }_e(x)$ 模拟编号为 $e$ 的机器在输入 $x$ 上的输出，就得到程序枚举。合法编码由通用机解释；无效编码可统一约定为处处发散程序。若有一个双参数程序 $P(a,x)$，参数化性质允许从 $P$ 的索引与常量 $a_0$ 机械生成新索引 $q$，满足

例如 $P(a,x)$ 先等待编号 $a$ 的程序在空输入上停机，再输出 $x+1$。即使这个等待永远不结束，编译器也能立即造出“内嵌常量 $a_0$，执行上述等待”的代码 $q$。编译的任务是产生有限描述，不是先算出描述的行为；混淆这两项任务会把停机问题错误地塞进参数定理。

边界在于任意双射或人为重排未必可接受。若编号把停机信息偷偷编码进索引位置，或者没有可计算的通用解释器，它即使集合论上枚举了所有偏函数，也不能支持程序变换定理。

映射 $e\mapsto {\phi }_e$ 不可能被当作可判定语义表。不同索引是否计算同一函数一般不可判定；也不能要求每个偏函数恰有一个索引，否则许多有效编程与固定点构造会失去所需的冗余。可接受性保证的是有效表达能力，不是程序等价判定器。

有效参数化被$s$-$m$-$n$ 定理理路s-m-n 定理s-m-n theorem · Parameter theorem把程序的部分输入有效固化为新程序索引的参数化定理。精确化：它把部分实参固化为新程序代码，同时保持代码变换本身总可计算。再结合对角式自应用，Kleene 递归定理理路Kleene 递归定理Kleene recursion theorem每个总可计算的程序代码变换都存在一个与其变换结果计算同一偏函数的程序索引。为每个总可计算代码变换构造语义固定点；Rice 定理理路Rice 定理Rice's theorem图灵可识别语言的每个非平凡语义性质都是不可判定的。则说明非平凡的部分可计算函数性质不可判定。

可接受编号统一枚举的是部分可计算函数理路部分可计算函数Partial computable function允许机器在函数未定义的输入上不停机的部分函数。，也就是允许发散的程序行为。不能把它改成只枚举全部总可计算函数的总解释器：若总可计算的 $U(e,x)$ 恰好覆盖这些函数，则 $g(n)=U(n,n)+1$ 也是总可计算函数；假如它是第 $k$ 行，便有 $U(k,k)=U(k,k)+1$，矛盾。

这套编号支持通用模拟、解释器和编译器的数学模型。递归定理中的固定点针对行为：对每个总可计算代码变换 $f$，都有某个 $e$ 满足 ${\phi }_e={\phi }_{f(e)}$，即使整数 $e$ 与 $f(e)$ 不同。