p103
無理数などの計算可能性
何かあるもの、たとえば、無理数、の計算可能性を考えるときは、計算誤差というもの（丸め誤差のこと、それ以外の誤差は理論では考えない）を注意深く考えに入れなくてはならない。大雑把に言うと、あるものが計算可能である、ということは、与えられた誤差の範囲内で結果を与えるアルゴリズム（きちんと決まった有限的な手段）があるということだ。M. B. Pour-El and J. I. Richards, Computability in Analysis and Physics (Springer, 1989)がこの話題についてはよい参考書である。
もっと実際の計算機に近く数字一つずつではなく、浮動点計算のように、「実数」をひとまとめにして計算可能性を扱うという行き方もあった [近づきやすい解説として, J. F. Traub, ``A continuous model of computation' Physics Today May, 1999, p39がある.]。これは特に最近、ブラム（Blum) ら[L. Blum, M. Shub and S. Smale, ``On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines,'' Bull. Amer. Math. Soc. 21 , 1-46 (1989); L. Blum, F, Cucker, M. Shub and S. Smale, Complexity and Real Computation (Springer, 1997).] によって有名になってきた。われわれがここで使う計算の理論、つまり、従来の計算の理論では、実数はいつも自然数列として扱われる。これと対照的に、この新しい計算の理論では実数は丸ごと一体として扱われる。ディジタル計算機の中では実数は一体として扱われるといっても、実際には有限桁の二進数であるから、計算時間などを問題にしないときは整数計算と変わることはない。そこで、この本では、計算の理論といえば、いつも従来の理論を指す。