計算可能数
計算可能数上の順序関係は計算可能でない。A を a {\displaystyle a} を近似するチューリングマシンの記述とする。このとき、任意に A を与えられて a > 0 {\displaystyle a>0} なら "YES"、 a ≤ 0. {\displaystyle a\leq 0.} なら "NO" を返せるようなチューリングマシンは存在しない。なぜかというと、 ε {\displaystyle \epsilon } 近似として0を出力し続けるマシン A を考えてみると、a が正であることを強制する近似を出力することはないと判断するまでの時間が不明なものになっている。それゆえ、このマシンは出力を得るためには最終的には a が 0 に等しいことを推測して出力しなければならないが、実際はそれを決めた後のタイミングで a が 0 でないことを強制する近似が判明してしまう可能性がある。このアイデアは全域関数を計算するいくつかの数列についてマシンが不正確であることを示すのに用いられる。似た問題がデデキント切断によって計算可能数を表現する際に発生する。等式関係は計算不可能である。