形式陈述

部分函数 $f:{\mathrm{\Sigma }}^{\ast }\rightharpoonup {\mathrm{\Sigma }}^{\ast }$ 称部分可计算，若存在图灵机：当 $x\in \mathrm{dom}(f)$ 时停机并输出 $f(x)$；当 $x\notin \mathrm{dom}(f)$ 时允许永不停止。其定义域必为可识别语言；反之，每个可识别语言都是某个部分可计算函数的定义域。全定义的部分可计算函数正是可计算函数。程序的操作语义通常自然给出从输入到输出的部分函数。

直觉

发散不是一个普通错误码，而是“没有结果”的计算行为。部分可计算性因此精确刻画可能不停机的真实程序，而不强迫为每个输入伪造输出。

例子与边界

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

推论与应用

该概念是递归可枚举集、通用程序、解释器与不可判定性的统一语言，也支撑域论和程序语义对终止信息的建模。

参考资料

• Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, 1987，Chs. 1–14。
• Robert I. Soare, Turing Computability: Theory and Applications, Springer, 2016，Chs. 1–5。