可计算数

在数学中，可计算的数字是可以通过有限的终止算法计算到任何所需精度的实数。 它们也被称为递归数、有效数或可计算实数或递归实数。

可以使用 μ 递归函数、图灵机或 λ 演算作为算法的形式表示来给出等效定义。 可计算的数字形成一个真实的封闭域，可以代替实数用于许多但不是所有的数学目的。

在下文中，Marvin Minsky 以类似于 Alan Turing 在 1936 年定义的方式定义了要计算的数字； 即，作为解释为 0 和 1 之间的小数的数字序列：

一个可计算的数字 [是] 一个有图灵机的数字，它在其初始磁带上给定 n，以该数字的第 n 个数字终止 [编码在其磁带上]。

定义中的关键概念是 (1) 在开始时指定了一些 n，(2) 对于任何 n，计算只需要有限的步骤，之后机器产生所需的输出并终止。

(2) 的另一种形式——机器连续打印其纸带上的所有 n 个数字，在打印第 n 个数字后停止——强调明斯基的观察：(3) 通过使用图灵机，有限定义——在 机器状态表的形式——被用来定义什么是潜在无限的十进制数字串。

然而，这不是现代定义，现代定义只要求结果准确到任何给定的精度范围内。 上面的非正式定义受到称为制表者困境的舍入问题的影响，而现代定义则不然。

一个实数 a 是可计算的，如果它可以通过一些可计算函数 f : N → Z {displaystyle f:mathbb {N} to mathbb {Z} } 以下列方式近似：给定任何正数 整数 n，该函数产生一个整数 f(n)，使得：

f ( n ) − 1 n ≤ a ≤ f ( n ) + 1 n 。 {displaystyle {f(n)-1 over n}leq aleq {f(n)+1 over n}。}

有两个相似的定义是等价的：

• 存在一个可计算函数，给定任何正有理误差边界 ε {displaystyle varepsilon } ，它产生一个有理数 r 使得 | r - 一个 | ≤ ε 。 {displaystyle |r-a|leq varepsilon .}
• 有一个可计算的有理数序列 q i {displaystyle q_{i}} 收敛到 {displaystyle a} 这样 | q i − q i + 1 | < 2 − i {displaystyle |q_{i}-q_{i+1}|<2{-i},} 对于每个 i。

通过可计算的 Dedekind 切割，还有另一个等效的可计算数字定义。

程序 D 给出了一个例子，它定义了 3 的立方根。

一个实数是可计算的当且仅当存在一个可计算的 Dedekind 割 D 与之对应。 函数 D 对于每个可计算的数字都是xxx的（当然两个不同的程序可能提供相同的函数）。

如果一个复数的实部和虚部是可计算的，则该复数被称为可计算的。

为每个图灵机定义分配一个哥德尔数会产生对应于可计算数的自然数子集 S {displaystyle S} 并识别从 S {displaystyle S} 到可计算数的满射。 图灵机只有可数个，说明可计算数是可数的。 然而，这些哥德尔数的集合 S {displaystyle S} 不可计算枚举（因此，根据它定义的 S {displaystyle S} 的子集也不是）。 这是因为没有算法可以确定哪些哥德尔数对应于产生可计算实数的图灵机。