可計算數

各式各樣的數

基本

$\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]

可計算數

目次

定義

不可計算數

相關條目

相關書籍

參考資料

引用

來源