可计算数

各种各样的数

基本

$\mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C}$

正数 $\mathbb {R} ^{+}$
自然数 $\mathbb {N}$
正整数 $\mathbb {Z} ^{+}$
小数
 有限小数
 无限小数
 循环小数
 有理数 $\mathbb {Q}$
代数数 $\mathbb {A}$
实数 $\mathbb {R}$
复数 $\mathbb {C}$
高斯整数 $\mathbb {Z} [i]$

负数 $\mathbb {R} ^{-}$
整数 $\mathbb {Z}$
负整数 $\mathbb {Z} ^{-}$
分数
 单位分数
 二进分数
 规矩数
 无理数
 超越数
 虚数 $\mathbb {I}$
二次无理数
 艾森斯坦整数 $\mathbb {Z} [\omega ]$

延伸

二元数
 四元数 $\mathbb {H}$
八元数 $\mathbb {O}$
十六元数 $\mathbb {S}$
超实数 $^{*}\mathbb {R}$
大实数
 上超实数

双曲复数
 双复数
 复四元数
共四元数（英语：Dual quaternion）
超复数
 超数
 超现实数

其他

素数 $\mathbb {P}$
可计算数
 基数
 阿列夫数
 同余
 整数数列
 公称值

规矩数
 可定义数
 序数
 超限数
 $p$ 进数
 数学常数

圆周率 $\pi =3.14159265$ …
自然对数的底 $e=2.718281828$ …
虚数单位 $i={\sqrt {-{1}}}$
无限大 $\infty$

可计算数（英语：computable numbers），是数学名词，是指可用有限次、会结束的算法计算到任意精确度的实数。可计算数也被称为递归数、递归实数或可计算实数。

等效的定义可以用递归函数、图灵机及λ演算等算法的形式表示法而得。可计算数形成实闭域，可以在许多数学应用上取代实数。

定义

如果一个实数 $a$ 能被某个可计算函数 $f:\mathbb {N} \to \mathbb {Z}$ 以下述方式来近似，那么 $a$ 就是一个可计算数：给定任何正整数 $n$ ，函数值 $f(n)$ 都满足：

{f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}

不可计算数

非可计算的实数即为不可计算数。1975年，计算机学家格里高里·柴廷（英语：Gregory Chaitin）做了一个有趣的实验：选择任意一种编程语言，随意输入一段代码，该代码能够成功运行并且能够在有限时间内终止的概率即为柴廷常数，这个数为一个经典的不可计算数。^[1]

参考资料

引用

^ 比根号2更“无理”的数 | 科学人 | 果壳网科技有意思. 2011-03-09 [2018-06-30]. （原始内容存档于2019-06-05）.

来源

Oliver Aberth 1968, Analysis in the Computable Number Field, Journal of the Association for Computing Machinery (JACM), vol 15, iss 2, pp 276–299. This paper describes the development of the calculus over the computable number field.
Errett Bishop and Douglas Bridges, Constructive Analysis, Springer, 1985, ISBN 0-387-15066-8
Douglas Bridges and Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.
Jeffry L. Hirst, Representations of reals in reverse mathematics, Bulletin of the Polish Academy of Sciences, Mathematics, 55, (2007) 303–316.
马文·闵斯基 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, NJ. No ISBN. Library of Congress Card Catalog No. 67-12342. His chapter §9 "The Computable Real Numbers" expands on the topics of this article.
E. Specker, "Nicht konstruktiv beweisbare Sätze der Analysis" J. Symbol. Logic, 14 (1949) pp. 145–158
Turing, A.M., On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 2 42 (1), 1936, 42 (1): 230–651937 [2018-08-22], doi:10.1112/plms/s2-42.1.230, （原始内容存档于2004-04-03） (and Turing, A.M., On Computable Numbers, with an Application to the Entscheidungsproblem: A correction, Proceedings of the London Mathematical Society, 2 43 (6), 1938, 43 (6): 544–61937, doi:10.1112/plms/s2-43.6.544 ). Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences.
Klaus Weihrauch 2000, Computable analysis, Texts in theoretical computer science, Springer, ISBN 3-540-66817-9. §1.3.2 introduces the definition by nested sequences of intervals converging to the singleton real. Other representations are discussed in §4.1.
Klaus Weihrauch, A simple introduction to computable analysis
H. Gordon Rice. "Recursive real numbers." Proceedings of the American Mathematical Society 5.5 (1954): 784-791.
V. Stoltenberg-Hansen, J. V. Tucker "Computable Rings and Fields" in Handbook of computability theory edited by E.R. Griffor. Elsevier 1999

[1] 比根号2更“无理”的数 | 科学人 | 果壳网科技有意思. 2011-03-09 [2018-06-30]. （原始内容存档于2019-06-05）.

[1]

查论编数的系统
可数集	自然数 ( $\mathbb {N}$ ) 整数 ( $\mathbb {Z}$ ) 有理数 ( $\mathbb {Q}$ ) 规矩数代数数 ( $\mathbb {A}$ ) 周期（英语：Period (algebraic geometry)）可计算数可定义数高斯整数 ( $\mathbb {Z} [i]$ ) 艾森斯坦整数
合成代数（英语：Composition algebra）	可除代数（英语：Division algebra）：实数 ( $\mathbb {R}$ ) 复数 ( $\mathbb {C}$ ) 四元数 ( $\mathbb {H}$ ) 八元数 ( $\mathbb {O}$ )
凯莱－迪克森结构	实数 ( $\mathbb {R}$ ) 复数 ( $\mathbb {C}$ ) 四元数 ( $\mathbb {H}$ ) 八元数 ( $\mathbb {O}$ ) 十六元数 ( $\mathbb {S}$ ) 三十二元数六十四元数一百二十八元数二百五十六元数……
分裂形式	于 $\mathbb {R}$ ：双曲复数分裂四元数分裂复四元数（英语：Split-biquaternion）分裂八元数（英语：Split-octonion）于 $\mathbb {C}$ ：双复数复四元数复八元数（英语：Bioctonion）
其他超复数	二元数二元四元数（英语：Dual quaternion）二元复数（英语：Applications of dual quaternions to 2D geometry）双曲四元数（英语：Hyperbolic quaternion）十六元数 ( $\mathbb {S}$ ) 三十二元数分裂复四元数（英语：Split-biquaternion）多重复数几何代数（英语：Geometric algebra）物理空间代数（英语：Algebra of physical space）时空代数（英语：Spacetime algebra）三元数无法良好构建六元数
其他系统	基数扩展自然数（英语：Extended natural numbers）无理数模糊数（英语：Fuzzy number）超实数列维-奇维塔域（英语：Levi-Civita field）超现实数超越数序数 $p$ 进数超自然数（英语：Supernatural number）上超实数（英语：Superreal number）
分类列表（英语：List of types of numbers）

可计算数

定义

不可计算数

相关条目

相关书籍

参考资料

引用

来源