形式陈述

对有限字母表上的全函数 $f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Sigma }}^{\ast }$，若存在确定性图灵机对每个输入 $x$ 都停机，并在输出带留下 $f(x)$，则 $f$ 可计算。自然数、元组或代数对象需先采用有效编码；不同可互相计算转换的合理编码给出同一可计算性概念。判定语言 $L$ 等价于计算其特征函数 ${\chi }_L$。多元函数可通过可计算配对编码化为一元函数。

直觉

可计算函数要求算法对每个合法输入都最终给出正确输出；“能验证某些结果”或“对大多数输入停止”都不够。它是算法可实现性的模型无关核心。

例子与边界

加法、最大公因数和有限图连通分量都是可计算函数。把程序映到其是否会在空输入上停机的比特不是可计算全函数。输出表示必须有效：若编码本身不可解码，形式上的字符串变换不能代表对象层面的算法。可计算并不意味着高效，Ackermann 函数可计算却增长极快；复杂性理论在此基础上进一步限制资源。

推论与应用

可计算函数用于定义算法、归约和有效结构；它把语言判定、数值计算与符号变换纳入统一框架，并为部分可计算函数和递归论奠定基线。

参考资料

• 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。