可计算函数

可计算函数是可计算性理论研究的基本对象。 可计算函数是算法直观概念的形式化模拟，从某种意义上说，如果存在可以完成函数工作的算法，则函数是可计算的，即给定函数域的输入，它可以返回相应的函数域 输出。 可计算函数用于讨论可计算性，而不涉及任何具体的计算模型，例如图灵机或寄存器机。 然而，任何定义都必须参考某些特定的计算模型，但所有有效定义都会产生同一类函数。产生可计算函数集的特定可计算性模型是图灵可计算函数和一般递归函数。

在对可计算函数进行精确定义之前，数学家们经常使用非正式术语“有效可计算”。 这个术语后来被认为是可计算的函数。 请注意，这些函数的有效可计算性并不意味着它们可以被有效计算（即在合理的时间内计算）。 事实上，对于一些可有效计算的函数，可以证明任何计算它们的算法都将非常低效，因为算法的运行时间会随着输入的长度呈指数增长（甚至超指数增长）。 可行的可计算性和计算复杂性研究可以有效计算的函数。

根据丘奇-图灵论题，可计算函数就是在给定无限量的时间和存储空间的情况下，可以使用机械计算设备计算的函数。 等效地，该论文指出，当且仅当函数具有算法时，该函数是可计算的。 请注意，这个意义上的算法被理解为一个人可以在无限时间和无限供应的笔和纸上执行的一系列步骤。

Blum 公理可用于定义关于可计算函数集的抽象计算复杂性理论。 在计算复杂性理论中，确定可计算函数的复杂性的问题被称为函数问题。

函数的可计算性是一个非正式的概念。 描述它的一种方法是说如果函数的值可以通过有效的过程获得，则该函数是可计算的。 更严格地说，函数 f : N k → N {displaystyle f:mathbb {N} {k}rightarrow mathbb {N} } 是可计算的，当且仅当存在一个有效的程序时， 给定任何自然数的 k 元组 x {displaystyle mathbf {x} }，将产生值 f ( x ) {displaystyle f(mathbf {x} )} 。 与此定义一致，本文的其余部分假定可计算函数将有限多个自然数作为参数并产生一个值，该值是单个自然数。

作为这种非正式描述的对应物，存在多种正式的数学定义。 可计算函数的类别可以在许多等效的计算模型中定义，包括

• 图灵机
• μ-递归函数
• Lambda 演算
• Post 机器（后图灵机和标签机）。
• 注册机器

尽管这些模型对函数、它们的输入和输出使用不同的表示，但任何两个模型之间都存在转换，因此每个模型本质上描述的是同一类函数，这导致人们认为形式可计算性既自然又不太好 狭窄。 这些函数有时被称为递归函数，与非正式术语可计算形成对比，这种区别源于 1934 年 Kleene 和 Gödel.p.6 的讨论

例如，可以将可计算函数形式化为 μ 递归函数，这些函数是采用自然数的有限元组并返回单个自然数的部分函数（就像上面那样）。 它们是最小的偏函数类，包括常量函数、后继函数和投影函数，并且在组合、原始递归和 μ 运算符下是封闭的。

等效地，可计算函数可以形式化为可以由理想化计算代理（例如图灵机或寄存器机）计算的函数。 形式上来说，部分函数 f : N k → N {displaystyle f:mathbb {N} {k}rightarrow mathbb {N} } 可以计算当且仅当存在计算机程序时 以下属性：

• 如果定义了 f ( x ) {displaystyle f(mathbf {x} )}，则程序将在输入 x {displaystyle mathbf {x} } 时终止，其值为 f ( x ) {displaystyle f(mathbf {x} )} 存储在计算机内存中。
• 如果 f ( x ) {displaystyle f(mathbf {x} )} 未定义，则程序永远不会在输入 x {displaystyle mathbf {x} } 时终止。