計算可能数
計算可能なデデキント切断を通した同値な定義も存在する。 計算可能なデデキント切断 とは、計算可能関数 D {\displaystyle D\;} であって、有理数 r {\displaystyle r} が入力として与えられると出力として D ( r ) = t r u e {\displaystyle D(r)=\mathrm {true} \;} か D ( r ) = f a l s e {\displaystyle D(r)=\mathrm {false} \;} を返すものであって次の条件を満たすものである。: ∃ r D ( r ) = t r u e {\displaystyle \exists rD(r)=\mathrm {true} \;}
∃ r D ( r ) = f a l s e {\displaystyle \exists rD(r)=\mathrm {false} \;}
( D ( r ) = t r u e ) ∧ ( D ( s ) = f a l s e ) ⇒ r < s {\displaystyle (D(r)=\mathrm {true} )\wedge (D(s)=\mathrm {false} )\Rightarrow r<s\;}
D ( r ) = t r u e ⇒ ∃ s > r , D ( s ) = t r u e . {\displaystyle D(r)=\mathrm {true} \Rightarrow \exists s>r,D(s)=\mathrm {true} .\;}
3 の 立方根を定めるプログラムはその一例である。 q > 0 {\displaystyle q>0\;} として、次のように定義する。:
p 3 < 3 q 3 ⇒ D ( p / q ) = t r u e {\displaystyle p^{3}<3q^{3}\Rightarrow D(p/q)=\mathrm {true} \;}
p 3 > 3 q 3 ⇒ D ( p / q ) = f a l s e . {\displaystyle p^{3}>3q^{3}\Rightarrow D(p/q)=\mathrm {false} .\;}
実数が計算可能であるとは、その実数に対応する計算可能なデデキント切断 D が存在することである。そのような関数 D は各計算可能数に対して一意的である。(しかしながらもちろん、二つの異なるプログラムがあってそれが同じ関数を与えることもある。) 複素数 が計算可能であるとは、実部と虚部が共に計算可能であることである。