29

それで、しばらく前に、次のようなジョークを読みました。

「絶対にバイナリで pi を計算しないでください。パイは無限に続き、ランダムであるため、理論的にはすべての有限ビット文字列が含まれます。そのため、存在するすべての著作物を所有し、深刻な罰金を科されることになります。」

これは明らかにユーモアを意図したものですが、考えさせられました。すべての有限ビット列が pi のバイナリ表現に存在する場合、これをデータ送信の方法として使用することは可能でしょうか?

たとえば、jpeg 画像として解釈できるビット文字列を送信したいとします。情報を直接送信する代わりに、pi の桁内でその位置を見つけ、pi の桁内の最初のビットの位置と文字列の長さを送信します。

これは私には非常に簡単なことのように思えますが、ここでの明らかな困難は、この文字列が最初の数兆桁でさえ見つかる可能性が非常に小さいことです。そのため、検索に膨大な時間がかかる可能性があります。

私の考えでは、複数のマシンを pi 内の大きなファイルの検索専用にして、すべての開始位置のインデックスを作成することができます。したがって、各計算は一度だけ行う必要があり、その情報はそれ以降非常に迅速に送信できます。

それで、あなたはどう思いますか？これは本当に実現可能ですか、それともこれらの計算に時間がかかりすぎますか?

読んでくれてありがとう！投稿ガイドラインを見落としていた場合はお詫び申し上げます。これがこのフォーラムでの最初の質問です。

編集：

迅速なご回答ありがとうございます。自分の推理に誤りがあると思ったのですが、その理由がわかってよかったです!

4

5 に答える 5

48

私のコメントを拡張します。ここには、情報エントロピーと呼ばれる非常に重要な概念があります。

完全な開示ではありませんが、私は 10 兆桁 (10^13) の Pi の桁数の現在の世界記録保持者です。

私は、全員の社会保障番号を約 10,000 コピー持っています。

しかし、だからといって、全員のアカウントにハッキングして ID を盗むことができるわけではありません。一人一人のSSNがどこから始まるか分からないからです。また、典型的な 9 桁の SSN の場合、その SSN が表示される Pi の最初の桁の長さは 9 桁程度になります。つまり、SSN に関する情報は、Pi 自体ではなくアドレスに保持されます。

たとえば、だれかが SSN を持っている場合: 938-93-3556

Piのオフセット597,507,393から始まります。その数597,507,393は、SSN 自体とほぼ同じ長さです。つまり、Pi を使用しても何も得られません。
(以前のオフセットが表示されるかどうかはわかりませんが、オフセットが小さいほど確率は指数関数的に減少します。)

これを一般化すると、無限桁の Pi (理論的には考えられるすべての情報を保持する) があったとしても、データ XXX を保持するアドレスは (非常に高い確率で) XXX 自体と同じ大きさになります。

つまり、情報は Pi 自体の数字ではなく、情報が始まるアドレスに保持されます。

于 2012-07-06T18:55:36.027 に答える
23

私たちはラウンジで退屈していたので<C++>、特定の長さの「メッセージ」の平均オフセットを見つけるために検索を実装しました。

100 万桁の Piをダウンロードし、固定長 (00..99 など) のすべてのサブシーケンスを探しました。メッセージの長さに応じて、次の出力が得られます。

 Digits    Avg.Offset    Unfound

 1            8.1        0
 2          107.07       0
 3          989.874      0
 4         9940.46       0
 5        99959.4        8 <-- note

検索された pi の桁数の 10% で、すでに見つかっていないパターンにヒットし始めることに注意してください。

また、情報エントロピーの法則によって予測されるように、平均オフセットはメッセージの長さにほぼ比例することに注意してください。

生の出力とタイミング:

ランニング

for a in 10 100 1000 10000 100000; do \make -B CFLAGS=-DNUMRANGE=$a && time ./test; done

ショー

g++ -DNUMRANGE=10 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
81 cumulative, 8.1 average

real    0m0.008s
user    0m0.008s
sys 0m0.004s
g++ -DNUMRANGE=100 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
10707 cumulative, 107.07 average

real    0m0.004s

g++ -DNUMRANGE=1000 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
989874 cumulative, 989.874 average

real    0m0.010s

g++ -DNUMRANGE=10000 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
9.94046e+07 cumulative, 9940.46 average

real    0m0.081s

g++ -DNUMRANGE=100000 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
8 unfound
9.99594e+09 cumulative, 99959.4 average

real    0m7.387s

完全なコード、makefile、および pi の数字: https://gist.github.com/3062541

于 2012-07-06T20:33:40.667 に答える
5

いいえ、ランダム シーケンス内の任意のシーケンスを効率的に見つけることはできません。これは、「ランダム」の定義から導き出されます。(シーケンスが発生した場所を予測する方法があれば、それはランダムではありません。)

すべての場所のインデックス作成に関しては、何を得ましたか? あなたは本質的に「開始点0にジャンプ...」と言っているので、「...そして、次のJPEGサイズのビットをπで計算します...」と言う必要があります（使用する必要があるため、勝ちはありません計算を行うエネルギーを増やす) または「...そして、メガ π インデックス内の次の JPEG サイズのデータ​​のチャンクを検索します。」(その場合は、JPEG ファイルを読み込むだけです。)

勝つことも、損益分岐点になることもありません (そして、ゲームから抜け出すことはできません)。

更新: @Mystial の答えは私のものよりも優れています。彼のポイント

たとえば、だれかが SSN を持っている場合: 938-93-3556

Pi のオフセット 597,507,393 から始まります。その番号 597,507,393 は、SSN 自体とほぼ同じ長さです。つまり、Pi を使用しても何も得られません。

根本的な問題をエレガントに捉えています。

于 2012-07-06T18:49:29.350 に答える
5

その発言は間違っています。円周率は無限大で、次の桁は予測できませんが、すべての可能な文字列がそこにあるというわけではありません。

たとえば、pi に似た関数を作成するとします。ただし、20 個のバイナリ ゼロのシーケンスがある場合は常に、次の 20 ビットを計算し、ゼロをそれに置き換えます。

そのシーケンスも無限であり、予測不可能ですが、20 個の 2 進ゼロのシーケンスが決して含まれていないことを確実に知ることができます。

PI に考えられるすべてのビット シーケンスが含まれていることを証明する方法はありません。

これも回答に役立つかもしれません: http://www.youtube.com/watch?v=8PUJvAlD64k

于 2012-07-06T18:50:41.270 に答える
1

無限に続き、ランダムであるため、理論的にはすべての有限ビット列が含まれます

Pi は無限に進みますが、間違いなくランダムではありません。その数字はサイズのプログラムで計算できますO(log n)(したがって、有限のプレフィックスはプレフィックスよりもはるかに小さいプログラムで生成できます)。これは、Pi のプレフィックスのコルモゴロフ複雑度がそれらのサイズよりも漸近的に小さいことを意味します。したがって、すべての有限文字列が含まれていることはまだ証明されていません (わかりません)。

于 2012-07-06T18:49:43.223 に答える