可計算數

各种各样的数

基本

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

延伸

其他

圓周率 $\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]