計算可能数
各チューリングマシンの定義にゲーデル数を割り当てることで計算可能数に対応する 自然数 部分集合 S {\displaystyle S} を生成し、 S {\displaystyle S} から計算可能数全体への全射を与える。チューリングマシンは可算個しかないので、計算可能数全体はsubcountableである。しかしながら,ゲーデル数の集合 S {\displaystyle S} それ自身は、計算可枚挙ではない (それゆえ、 S {\displaystyle S} の部分集合でSを基に定義されるものも計算可枚挙ではない)。これは計算可能実数を生成するチューリングマシンに対応するゲーデル数を決定するアルゴリズムは存在しないためである。計算可能実数を生成するためには、チューリングマシンは全域関数を計算しなければならない、しかし、対応する決定問題はチューリング次数 が 0′′ である。結論として、自然数の集合から計算可能実数の集合への全射計算可能関数は存在しない。 実数全体の集合は不可算であって、計算可能数の集合は可算であり、ほとんど全ての 実数は計算可能ではない。ここで、任意の与えられた計算可能数 x {\displaystyle x} について、整列原理によって S {\displaystyle S} の極小要素で x {\displaystyle x} に対応するものが存在する。そして、それゆえそのような極小なゲーデル数からなる部分集合から計算可能数全体への全単射が存在する. この全単射の逆写像は計算可能数に対応する自然数の集合への単射である。しかし、前述の通りこの部分集合は計算可能実数が整列されていても計算可能ではない。
完全な順序関係は計算不可能である一方、異なる数のペアに限定すれば大小関係は計算可能である。すなわち、次のようなプログラムは存在する。チューリングマシン A, B が実数 a {\displaystyle a} , b {\displaystyle b} ただし a ≠ b {\displaystyle a\neq b} であるものを計算するものとしてそれが入力として与えられる、これに対して出力は a < b {\displaystyle a<b} か a > b {\displaystyle a>b} を与えるものである。これには、 ε < | b − a | / 2 {\displaystyle \epsilon <|b-a|/2} である ε {\displaystyle \epsilon } -近似を用いれば十分でこの ε {\displaystyle \epsilon } は0にいくらでも近づけられる。 a ≠ b {\displaystyle a\neq b} である以上は、最終的に a < b {\displaystyle a<b} か a > b {\displaystyle a>b} は必ず判断できる。