可计算函数

在可计算性理论中，可计算函数或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确，并且依据邱奇-图灵论题它们严格的是使用机器计算设备可计算的函数。函数的可计算性的概念可以相对化为任意自然数的集合 A，或等价的从自然数到自然数的任何函数 f，通过使用带有 A 或 f 的 oracle 扩展的图灵机。这种函数也可以分别叫做 A-可计算的 或 f-可计算的。在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。

使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。可以使用 Blum 公理来在可计算函数的集合上定义抽象计算复杂性理论。

依据邱奇-图灵论题，可计算函数的类等价于递归函数、lambda 演算或马尔可夫算法定义的函数类。

它们也可以被定义为能用图灵机、Post 系统或寄存器机运算的那些算法。

在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做函数问题。

定义

偏函数

f:\subseteq \mathbb{N} \to \mathbb{N}

被称为可计算的，如果

f

的图是递归可枚举集合。带有一个参数的偏可计算函数的集合通常表示为

\mathbf{P}^{(1)}

，或

\mathbf{P}

如果参数的数目在上下文中是明确的。

全函数

f:\mathbb{N} \to \mathbb{N}

被称为可计算的，如果

f

的图是递归集合。带有一个参数的全可计算函数的集合通常表示为

\mathbf{R}^{(1)}

或

\mathbf{R}

。

可计算函数 $f$ 被称为可计算谓词，如果它是布尔值函数，就是

f:\subseteq \mathbb{N} \to \{0,1\}

注解

有时出于清晰的原因，我们把可计算函数写为

g:\subseteq \mathbb{N}^k \to \mathbb{N}

我们轻易的使用配对函数编码 g 为新函数

f:\subseteq \mathbb{N} \to \mathbb{N}

例子

常函数 f : N^k→ N, f(n₁,...n_k) := n

加法 f : N²→ N, f(n₁,n₂) := n₁ + n₂

最大公约数
贝祖等式，线性的丢番图方程。

性质

可计算函数的集合是可数集合。

给定两个函数 f 和 g，则 f+g、fg 和 f $\circ$ g 是可计算函数。

可计算函数是算术可定义的。

布尔值函数 f 是可计算谓词，当且仅当语言 $\{x \in \Sigma^{*} : f(x)=1\}$ 是递归语言。

递归论 | 計算理論

Computable function | Fonction calculable | Funzione calcolabile | 計算可能関数

Gourt Home::Gourt :: 可计算函数

定义

注解

例子

性质