計算可能数
計算可能数上の算術的操作はそれら自身計算可能である。すなわち、計算可能実数 a と b が存在するとき、次の数は全て計算可能である: a + b, a - b, ab, そして b が 0 でない場合の a/b。これらの操作は実際のところ 一様計算可能 である; 例えば、チューリングマシンで入力が (A,B, ε {\displaystyle \epsilon } ) で出力が r であるものがある。ここで A は a を、B は b を近似するチューリングマシンの記述で、r は a+b の ε {\displaystyle \epsilon } 近似である。 この計算可能実数が体をなすということはHenry Gordon Riceによって1954年に初めて証明された。 計算可能実数全体は計算可能体はなしていない。計算可能体の定義には実効的な等価性が必要である。
実数 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 a\leq {f(n)+1 \over n}.}
となるように与えること。 この定義には、これと同値な二つの別の定義も存在する。:
与えられたいかなる有理誤差限界 ε {\displaystyle \varepsilon } に対しても有理数 r を | r − a | ≤ ε {\displaystyle |r-a|\leq \varepsilon } であるように生成するような計算可能関数が存在すること。
有理数の計算可能列 q i {\displaystyle q_{i}} であって、 a {\displaystyle a} に収束してさらに各 i に対して | q i − q i + 1 | < 2 − i {\displaystyle |q_{i}-q_{i+1}|<2^{-i}\,} が成り立つものが存在すること。