可计算函数 编辑
在可计算性理论中，可计算函数或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。
1
相关
递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论有所重叠。
阿隆佐·邱奇是美国数学家，1936年发表可计算函数的第一份精确定义，对算法理论的系统发展做出巨大贡献。邱奇在普林斯顿大学受教并工作四十年，曾任数学与哲学教授。1967年迁往加利福尼亚大学洛杉矶分校。
阿隆佐·邱奇是美国数学家，1936年发表可计算函数的第一份精确定义，对算法理论的系统发展做出巨大贡献。邱奇在普林斯顿大学受教并工作四十年，曾任数学与哲学教授。1967年迁往加利福尼亚大学洛杉矶分校。
在计算复杂性理论，间隙定理，又称鲍罗丁－特拉赫坚布罗特间隙定理，为与可计算函数复杂度有关的重要定理。
阿隆佐·邱奇是美国数学家，1936年发表可计算函数的第一份精确定义，对算法理论的系统发展做出巨大贡献。邱奇在普林斯顿大学受教并工作四十年，曾任数学与哲学教授。1967年迁往加利福尼亚大学洛杉矶分校。
递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论有所重叠。
在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义建立在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。
超计算或超图灵计算可以输出非可计算函数结果的计算模型。例如，一台可以解决停机问题的机器可算作一台超计算机；可以可判定性皮亚诺公理中每一个状态的机器亦然。
结构化程式理论也称为伯姆-贾可皮尼理论或Böhm-Jacopini理论，是一项程式语言研究的结果，说明只要一种程式语言可以依三个方式组合其子程式及调整控制流程，每个可计算函数都可以用此种程式语言来表示。三个调整控制流程的方式为
在计算复杂性理论，布卢姆加速定理为关于可计算函数复杂度的基本定理，最早由曼纽尔·布卢姆在1967年提出。