書評(数理論理学)

教科書など

計算可能性解析学

おまけ

田崎さんの問いかけへの回答案です。

その実数に十分速く収束する有理数の列を生成するプログラムで実数を表現する大技があります。これが、計算機での実数の表現で実行可能なもののうち、もっとも多くの実数を表現可能なものになるものであろうというのは、直観的に納得できると思います。それを計算可能性理論の言葉を使ってきっちり定義したのが、計算可能実数です。

計算可能実数全体が実閉体をなすことが、すでにわかっています。その系として、すべての代数的実数が計算可能実数であることが、すぐに出ます。また、無限級数として表わせば、円周率も自然対数の底も計算可能実数であることが、すぐにわかります。その他、解析学で普通に出てくる多くの実数が計算可能実数であることがわかります。

しかし、プログラム全体は可算無限個しかないのに実数全体は連続無限個なので、計算可能実数は実数のごく一部です。


一つ上に戻る
書評のトップページ
鴨 浩靖