計算可能数
マービン・ミンスキーは数の計算可能性をアラン・チューリングが1936年に行ったのと同様の方法で以下のように定義した; すなわち、0から1の間にある "十進小数と見なせる数列"として:。
この定義における重要な点は (1) 最初にある n を決めておくこと、(2) いかなる n に対しても有限ステップ後、マシンが望まれた出力をして停止することである.
(2) の代わりに次のようなものがある – マシンが n 桁全てを連続でテープに出力した後、n桁目を出力した後停止する – これは次のミンスキーの観察を強調する: (3) チューリングマシンを用いることによって、状態遷移図の形をした "有限的" な定義が 無限 の長さになるかもしれない十進小数を定義するのに用いられる。
これはしかしながら、与えられた任意精度内に計算結果を収めることのみを要求する現代的な定義とは異なる。上で記した非形式的な定義はtable-maker's dilemmaと呼ばれる丸め誤差の問題の影響を受けるが、現代的な定義はそうではない。
計算可能実数の集まりは解析で使われる実数の性質を満たすとは限らない。例えば、計算可能実数からなる有界な増加列があってもその上限は計算可能実数であるとは限らない。 この性質を満たす数列はSpecker sequenceとして知られている。これはErnst Speckerによって1949年に構成された。 このような反例がある一方、実解析の一部は計算可能数の分野で発展し計算可能解析学の研究に繋がっている。
全ての計算可能数は算術的定義可能であるが逆は成り立たない。算術的定義可能であるが計算可能でない実数はたくさん存在する。例えば:
any number that encodes the solution of the 停止問題 (や他の 決定不能問題) の解を選ばれた符号化方式で符号化している数。
チャイティンの定数, Ω {\displaystyle \Omega } , これは停止問題とチューリング同値であるような実数の一種である。
これらの例は実際のところ、定義可能かつ計算不能な数の無限集合を定義し、各万能チューリングマシンごとに一つずつ与える。 実数が計算可能であるとき、かつその時に限り、自然数の集合を特性関数として見なしたとき計算可能である。
計算可能実数全体は (およびそのうち可算な稠密順序で端点の無い部分集合は) 有理数全体と順序同型である。