有界判定時間は有理数になりますか？

質問

http://oshiete1.goo.ne.jp/qa4246891.html
を解答していて疑問に思いました。

有理数⇔循環小数はなりたちますが
小数点以下の各位が有限時間で分るとしても有理数とは限りません。
(例 私の回答)
ですが、各位の数値を求める時間がある有限時間以内であれば、
有理数になるのではないかと考えましたが、このようなことは証明できるのでしょうか？
(否定の場合も否定であることを証明できるのでしょうか？)

回答No.4

Tacosan · ベストアンサー

「a(n) を計算するときの計算時間」をきちんと定義しないとだめです.
例えば, 「n を 3 で割った余りを求める」ときの計算時間はどうしましょうか? 計算量理論の立場で言うと, 「n が小さい場合」のみを考えていいなら定数時間としてしまいますが, n が非常に大きい場合も考慮するときには O(log n) 時間かかると考えるのが, おそらく普通でしょう.

お礼

ありがとうございます。
例の「n を 3 で割った余りを求める」の計算時間は桁数に比例すると考えてO(log n) 時間と考えるのは妥当だと思います。

回答No.5

Tacosan

「各位の数値を求める時間」としてその定義を採用する場合, 「n桁目」の値を計算するときには「n を表す表記」における有限個の桁しか調べることができません. その最上位を N桁目とすると, 「n を表す表記」において N+1 桁目以上は全くチェックされません. つまり,
a(n) = a(n+10^(N+1)) = a(n+2・10^(N+1)) = ...
がなりたちますから, 自動的に循環小数 (= 有理数) になります.
ただし, 全ての有理数がこのようにチェックできるわけではないというのもポイント.

お礼

ありがとうございます。
お礼が遅れてすみませんでした。
いろいろいな考え方を吸収していきます。

回答No.3

gef00675

a(n)が構成可能な式かどうかは、nの表記法にも関係しそうな気がします。

nを十進数で表したときの最も位の大きい桁の数をa(n)と定義したとき、aは、
a=0.123456789 1111111111 2222222222 …
となりますが、これは有理数ではありません。
これは、あなたの「有限判定時間」な数ではありませんか？

お礼

ありがとうございます。
たしかに仰るような反例もあったんですね。
nが始めから10進数で表示されていれば、1ステップで確認できますね。
ですが、一方で構成可能とは具体的にどういうことか議論を尽くしていませんが、
全ての自然数を0から出発して+1ずつして進んでいくと考えるとnの10進表記を求める時間も(nが無限大になると)、無限大になっていきます。

回答No.2

tecchan22

実数ａに対し，ａの１０進表示（２進表示でもよい）における小数第ｎ位の数が，あるプログラムによってｎの値に関わらずある定数以下の時間（ステップ）により計算できるとき，ａは有理数と言えるか？という問題ですね。

これは言えそうな気もするが・・

定数でなく，多項式時間（つまり，logn のある多項式以下の時間）ならば，多くの無理数が計算できますがね。

お礼

ありがとうございます。
まず、問題の定式化を試みました。

実数のaの小数第n位をa(n)とします。
そしてa(n)は構成可能な式で定義されているとします。
a(n)を計算する最小ステップ数をT(n)とします。
limT(n)＝∞ ⇒ 無理数
T(n)は有界 ⇒ 有理数

ここで「構成可能な式」を正確に捉えることが私にとって難関です。

回答No.1

Tacosan

? 今一つ意味がとれない....
「各位の数値を求める時間がある有限時間以内」というのは, 「各位が有限時間でわかる」とは違うのですか?

お礼

ありがとうございます。
質問の意味はANO2の方のご説明の通りです。
実数のaの小数第n位をa(n)とします。
そしてa(n)は構成可能な式で定義されているとします。
a(n)を計算する最小ステップ数をT(n)とします。
limT(n)＝∞ ⇒ 無理数
T(n)は有界 ⇒ 有理数
なのかなと思ったりしていますが
やはり、味噌は、まず「構成可能な式」を正確に捉えることでしょうか？