可計算數

可計算數（英語：computable numbers），是數學名詞，是指可用有限次、會結束的演算法計算到任意精確度的實數。可計算數也被稱為遞迴數、遞迴實數或可計算實數。

各式各樣的數

基本

${\displaystyle \mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C} }$ 正數 ${\displaystyle \mathbb {R} ^{+}}$ 自然數 ${\displaystyle \mathbb {N} }$ 正整數 ${\displaystyle \mathbb {Z} ^{+}}$ 小數 有限小數 無限小數 迴圈小數 有理數 ${\displaystyle \mathbb {Q} }$ 代數數 ${\displaystyle \mathbb {A} }$ 實數 ${\displaystyle \mathbb {R} }$ 複數 ${\displaystyle \mathbb {C} }$ 高斯整數 ${\displaystyle \mathbb {Z} [i]}$ 負數 ${\displaystyle \mathbb {R} ^{-}}$ 整數 ${\displaystyle \mathbb {Z} }$ 負整數 ${\displaystyle \mathbb {Z} ^{-}}$ 分數 單位分數 二進分數 規矩數 無理數 超越數 虛數 ${\displaystyle \mathbb {I} }$ 二次無理數 艾森斯坦整數 ${\displaystyle \mathbb {Z} [\omega ]}$

延伸

二元數 四元數 ${\displaystyle \mathbb {H} }$ 八元數 ${\displaystyle \mathbb {O} }$ 十六元數 ${\displaystyle \mathbb {S} }$ 超實數 ${\displaystyle ^{*}\mathbb {R} }$ 大實數 上超實數 雙曲複數 雙複數 複四元數 共四元數（英語：Dual quaternion） 超複數 超數 超現實數

其他

質數 ${\displaystyle \mathbb {P} }$ 可計算數 基數 阿列夫數 同餘 整數數列 公稱值 規矩數 可定義數 序數 超限數 p進數 數學常數 圓周率 ${\displaystyle \pi =3.14159265}$… 自然對數的底 ${\displaystyle e=2.718281828}$… 虛數單位 ${\displaystyle i={\sqrt {-{1}}}}$ 無限大 ${\displaystyle \infty }$

閱 論 編

等效的定義可以用遞迴函數、圖靈機及λ演算等演算法的形式表示法而得。可計算數形成實閉體，可以在許多數學應用上取代實數。

定義

如果一個實數${\displaystyle a}$能被某個可計算函數 ${\displaystyle f:\mathbb {N} \to \mathbb {Z} }$ 以下述方式來近似，那麼 ${\displaystyle a}$ 就是一個可計算數：給定任何正整數${\displaystyle n}$，函數值${\displaystyle f(n)}$都滿足：

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

不可計算數

非可計算的實數即為不可計算數。1975年，計算機學家格里高里·柴廷（英語：Gregory Chaitin）做了一個有趣的實驗：選擇任意一種程式語言，隨意輸入一段程式碼，該程式碼能夠成功運行並且能夠在有限時間內終止的機率即為柴廷常數，這個數為一個經典的不可計算數。^[1]

相關條目

• 可定義數
• 可計算函數、半可計算函數（英語：Semicomputable function）
• 超計算問題（英語：Transcomputational problem）

相關書籍

• 科学技朮的哲学反思. 清華大學出版社有限公司. 2004: 119 [2018-06-30]. ISBN 978-7-3020-8560-7. （原始內容存檔於2019-06-17）.

參考資料