Computable Function
定义 Definition
computable function（可计算函数）：在计算理论中，指一种存在算法（等价地，可由图灵机/递归程序实现）来计算其输出的函数。也就是说，对任意允许的输入，算法会在有限步骤内停机并给出正确结果。（在更广义语境下也可讨论“部分可计算函数”，对某些输入可能不停止。）
发音 Pronunciation (IPA)
/kəmˈpjuːtəbl ˈfʌŋkʃən/
例句 Examples
A computable function can be calculated by an algorithm.
可计算函数可以通过算法计算出来。
In computability theory, we prove that some problems cannot be solved by any computable function, even if we allow unlimited time and memory in theory.
在可计算性理论中，我们证明有些问题无法由任何可计算函数解决，即使在理论上允许无限的时间与内存。
词源 Etymology
computable 来自 compute（计算）+ 后缀 -able（“能够……的”），表示“可被计算的”；function 源自拉丁语 functio（执行、作用），在数学中指“输入到输出的对应规则”。合起来在现代逻辑与计算理论语境中专指“可由有效过程（算法）实现的函数”。
相关词 Related Words
文学与经典著作 Literary Works
- Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem（1936）：以“可计算数/可计算过程”为核心框架，奠定“可计算函数”思想基础。
- Alonzo Church, An Unsolvable Problem of Elementary Number Theory（1936）：与λ演算相关，提出与“可计算”概念等价的表述。
- Stephen C. Kleene, Introduction to Metamathematics（1952）：系统化递归函数/可计算函数理论。
- Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability（1967）：经典教材，频繁使用“computable function”。
- Michael Sipser, Introduction to the Theory of Computation（多版）：以教学方式讲解可计算函数、可判定性与不可判定性。
Select Language