numbers - PI は計算可能なチューリング数ですか?

Question

私の知る限り、計算可能な数値のチューリングは、チューリング マシンによって i 番目のインデックスを返すことができる数値です。したがって、計算不可能な数値は、他のプログラムが他の入力で停止した場合などに小数点が決定される数値のようなものになります。ただし、PI は実数であり、TM によって列挙できないため、計算されますか？では、どの学派が正しいのでしょうか？

Answer 1

はい、π計算可能です。計算可能の同等の定義がいくつかありますが、ここで最も役立つのは上で示したものです。実数は、その1 桁目rを見つけるアルゴリズムが存在する場合、計算可能です。これがそのようなアルゴリズムです。n

あなたの最後の議論は適切ではありません。「番目の数字を見つけることができる」という定義nを「すべての数字を列挙できる」と混同しています。後者は有用な定義ではありません。すべての無理数と多くの有理数も除外します!

興味深い事実は、計算可能な数が実際に数えられるということです。なぜなら、それらを生成するチューリング マシンをゲーデル数えることができるからです。したがって、計算可能な実数はほとんどありません。