可计算函数

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

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

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

可计算不意味着高效。Ackermann 函数在每个自然数输入上都有值且可由算法求出，却增长得极快；一个穷举算法也可能需要难以承受的时间。复杂性理论正是在总可计算的基础上再限制资源，而不是把“慢”重新归为“不可计算”。

存在定义明确却不可计算的全函数。例如令 $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所有有效可计算过程都可由图灵机计算的经验性等价主张。。在具体数学结构上谈“可计算”时，还需随结构一起给出有效表示；仅声明抽象对象之间存在一个集合论函数，无法产生可执行过程。