部分可计算函数

部分可计算函数允许算法在定义域之外永不返回，这精确表达了搜索式计算：找到见证时输出，找不到时可能无限继续。发散不是普通错误码，而是“没有结果”的计算行为；它把“未定义”与“返回某个特殊错误值”严格区分，后者仍是一个全函数值，前者则对应没有终止计算。因此，部分可计算性能够刻画可能不停机的真实程序，而不必为每个输入伪造输出；许多自然程序首先以这种形式出现，再通过额外证明确认它在目标输入域上总停机。

令 $f(P,x)$ 在程序 $P$ 对输入 $x$ 停机时返回其输出，否则未定义；这是通用函数模拟公理库通用图灵机Universal Turing machine输入机器编码和输入串后模拟该机器运行的图灵机。给出的部分可计算函数，但其定义域就是停机语言，不可判定。若机器在域外明确拒绝并停机，则仍计算一个全函数（例如带错误标记的结果），不是靠发散定义的部分函数。部分可计算函数相等要求定义域相同且域内输出相同；仅在共同终止输入上一致不够。

定义 $\phi (M,w)$：模拟 $M(w)$，若停机则输出其步数，否则不定义。该函数可由通用模拟器部分计算，但若能把它扩成一个同时正确判断“不定义”的全可计算过程，就会判定停机问题。最小化算子也常产生部分函数：搜索最小 $y$ 使谓词 $R(x,y)$ 成立，若不存在这样的 $y$，搜索不终止。

当 $R$ 是可判定谓词时，这个搜索可明确写成依次测试 $y=0,1,2,\dots$，第一次为真就返回 $y$。取 $R(x,y)$ 为 $y^2=x$：输入 $9$ 依次排除 $0,1,2$ 后返回 $3$；输入 $2$ 则永远没有成功测试。若把测试器换成仅可识别的 $R$，第一个不成功的候选就可能卡住，所以这项顺序最小化的前提必须保留。

若谓词及搜索上界都能原始递归地计算，有界搜索在失败时返回约定值，仍可属于原始递归函数公理库原始递归函数Primitive recursive function · Primitive recursion从零、后继和投影函数出发，有限次使用复合与原始递归构造出的自然数全函数。类；去掉界则需要另行证明终止。有界与无界的差别不能只从程序中是否出现循环判断。

不要把部分可计算误解为“机器可能随机失败”或“实现有 bug”。定义域本身是数学对象，且在定义域内必须给出确定的正确值；多值关系和概率输出属于其他模型。

部分可计算性是递归可枚举集、通用程序与不可判定性的统一语言。可接受编号公理库程序编号与可接受编号Program indexing · Acceptable numbering · Gödel numbering对部分可计算函数进行有效枚举，并要求编号支持通用解释与有效参数编译。把这些偏函数排成可被通用解释器处理的有效序列，而$s$-$m$-$n$ 定理公理库s-m-n 定理s-m-n theorem · Parameter theorem把程序的部分输入有效固化为新程序索引的参数化定理。在索引层完成参数固化；两者不改变函数可能发散的语义。可识别语言公理库可识别语言Turing-recognizable language · Recursively enumerable language存在图灵机对语言内输入接受、对语言外输入可拒绝或不停机的语言。可由部分特征函数刻画——成员返回 $1$，非成员允许不停止——因此部分可计算性正是递归可枚举现象的函数版本。