可计算函数

可计算函数把算法从“接受或拒绝一个语言”的二值形式推广到产生任意有限输出，是算法可实现性的模型无关核心。图灵机不必一次写出整个答案，可以通过有限步符号操作逐步构造结果；停机时输出带上的内容才是函数值。总性则像一份覆盖整个输入域的终止合同：每个输入都必须沿某条有限计算轨迹抵达答案，不能把发散当作隐藏的第三种返回值。

这一区分也解释了为什么“程序能算出我关心的那些例子”还不够。若输入域声明为全部 ${\mathrm{\Sigma }}^{\ast }$，机器在某个罕见输入上无限循环，得到的仍只是部分函数。反过来，运行时间极长不损害可计算性，只要每个固定输入最终停机；效率要由后续时间、空间复杂度另外衡量。

函数 $f(n)=n+1$ 在一元编码下可由扫描输入末尾并再写一个 1 的机器计算；二进制编码需处理进位，但对每个有限输入仍会结束。加法、最大公约数、字符串反转，以及把有限图编码映到其连通分量列表，都是可计算全函数。这些例子显示输入、输出表示同样重要：若所谓编码无法有效解码，字符串上的形式变换便不能自动代表对象上的算法。

语法树求值必须先限定语言。例如只允许自然数常量、加法和乘法的有限表达式树，求值器先求两个严格更小的子树，再执行算术运算。树 $(2+3)\times 4$ 先得到子值 $5$ 与 $4$，再得到 $20$；对节点数归纳即可证明总停机。若语法允许任意循环或递归调用，树本身有限却不保证执行终止，通用程序求值器通常只计算偏函数。除法还需要处理除零，不能凭“树有限”跳过运算的定义域。

可计算不意味着高效。Ackermann–Péter 函数在每个自然数输入上都有值且可由算法求出，却不属于原始递归函数公理库原始递归函数Primitive recursive function · Primitive recursion从零、后继和投影函数出发，有限次使用复合与原始递归构造出的自然数全函数。类；后者从基本函数经有限次复合与受限递归构造，并不穷尽全可计算函数。Ackermann–Péter 函数也增长得极快；一个穷举算法也可能需要难以承受的时间。复杂性理论正是在总可计算的基础上再限制资源，而不是把“慢”重新归为“不可计算”。

存在定义明确却不可计算的全函数。例如令 $h(e,x)=1$ 当编号为 $e$ 的机器在输入 $x$ 上停机，否则为 $0$。每对 $(e,x)$ 都有唯一的布尔值，但若 $h$ 可计算，就得到停机问题判定器。这里“数学上处处有值”只说明它是全函数，不蕴含存在能在每个输入上把该值算出来的算法。

边界还包括故意返回错误标记的程序。若机器对非法或失败输入返回 error 并停机，它计算的是到扩展输出域 ${\mathrm{\Sigma }}^{\ast }\cup \{\mathtt{error}\}$ 的全函数；若它在这些输入上发散，才是部分函数。两种接口可以服务不同目的，却不能只因源码都含循环就混为同一语义。

可计算全函数为映射归约公理库映射归约Mapping reduction · Many-one reduction用可计算函数把一个语言成员关系变换为另一个语言成员关系。提供实例翻译器：若变换可能在某些源实例上发散，就不能保证归约算法完成。布尔输出的全函数对应语言判定；部分可计算函数公理库部分可计算函数Partial computable function允许机器在函数未定义的输入上不停机的部分函数。的定义域则对应语言识别。这一总函数／部分函数分层让终止义务、语言分类和程序语义各自落在正确位置。

图灵机公理库图灵机Turing machine通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。、递归函数与 λ 演算对有效计算给出等价刻画，并支撑Church–Turing 论题公理库Church–Turing 论题Church–Turing thesis把非形式的有效计算过程与图灵可计算性联系起来的论题。。在具体数学结构上谈“可计算”时，还需随结构一起给出有效表示；仅声明抽象对象之间存在一个集合论函数，无法产生可执行过程。

全可计算函数对复合封闭：先算 $f(x)$，再把所得有限字交给 $g$，两次总性合起来保证 $g(f(x))$ 返回。若只知道二者偏可计算，还须满足 $x\in \mathrm{dom}(f)$ 和 $f(x)\in \mathrm{dom}(g)$。“每个步骤都有程序”因此不是整个调用链的总性证明。

极限可计算函数公理库极限可计算函数Limit-computable function · Computable in the limit · Limit recursive function允许可计算猜测有限次改口、只要求每个输入最终稳定到正确值的总函数。用总可计算 $g(x,s)$ 逐点最终稳定到 $f(x)$，但不要求算法知道稳定时刻。普通可计算函数都能用恒定近似表示；停机集特征函数有可计算稳定近似，却没有普通总算法。因此“最终不再改口”和“在可观察的停机时刻给出答案”提供不同的计算能力。