可计算性理论 编辑
递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论有所重叠。
1
相关
算术阶层是递归论或可计算性理论中的概念，将自然数的子集按照定义它们的公式的复杂度分类。
在可计算性理论与计算复杂性理论中，所谓的归约是将某个计算问题转换为另一个问题的过程。可用归约法定义某些问题的复杂度类。
在可计算性理论与计算复杂性理论中，所谓的归约是将某个计算问题转换为另一个问题的过程。可用归约法定义某些问题的复杂度类。
在可计算性理论中，原始递归函数对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和函数复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。
在可计算性理论中，原始递归函数对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和函数复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。
在可计算性理论与计算复杂性理论中，决定性问题，亦称判定问题，是一个在某些形式系统回答“是”或“否”的问题。
在可计算性理论与计算复杂性理论中，所谓的归约是将某个计算问题转换为另一个问题的过程。可用归约法定义某些问题的复杂度类。
在可计算性理论，如果一系列操作数据的规则可以用来模拟任何图灵机，那么它是图灵完备的。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。如今，几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。
不可解度，或图灵度，是数学逻辑的名词，尤其应用在可计算性理论中。
在可计算性理论，如果一系列操作数据的规则可以用来模拟任何图灵机，那么它是图灵完备的。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。如今，几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。