可以在合理的时间内在pi中找到任何有限位串吗？

Question

所以,不久前我读了一个像这样的笑话:

"永远不要用二进制来计算pi - 因为它无限地进行并且是随机的,它理论上包含每个有限的位串.因此,你将拥有所有受版权保护的材料,并承担一些严重的罚款."

这显然是幽默的,但它让我思考.如果每个有限位串都存在于pi的二进制表示中,是否可以将其用作传输数据的方法？

例如,假设我想传输一个可以解释为jpeg图像的位字符串.我不是直接发送信息,而是在pi的数字内找到它的位置,并简单地发送pi数字中第一位的位置,以及字符串的长度.

这对我来说似乎很简单,但这里显而易见的问题是,即使是前几万亿个数字内找到这个字符串的概率也非常小.因此,最终可能需要花费大量时间才能找到.

我的想法是,几台机器可以专门用于在pi中搜索大文件,然后创建所有起始位置的索引.因此,每次计算只需要发生一次,然后从那时起可以非常快速地传输该信息.

所以你怎么看？这完全可行,还是这些计算需要花费太多时间？

谢谢阅读!如果我忽略了任何发布指南,我会道歉,如果我在这个论坛中提出第一个问题.

编辑:

感谢您的快速回复,伙计们!我认为我的推理有错误,很高兴知道为什么!

Answer 1

扩展我的评论.这里有一个非常重要的概念叫做信息熵.

出于完全披露,我是目前世界纪录保持者的Pi数字为10万亿位数(10 ^ 13).

我有大约10,000份每个人的社会安全号码.

然而,这并不意味着我可以侵入每个人的账户并窃取他们的身份.因为我不知道每个人的SSN 在哪里开始.对于典型的9位SSN,Pi中将出现SSN的第一个数字将是9位数的长度.换句话说,有关SSN的信息保存在地址中而不是Pi本身.

例如,如果有人拥有SSN:938-93-3556

它起始于Pi的597,507,393.这个数字597,507,393与SSN本身一样长.换句话说,我们通过使用Pi获得了什么.
_{(我不确定它出现的是否存在较早的偏移,但是随着偏移量的减小,概率会呈指数级下降.)}

为了概括这一点,即使你有Pi的无限数字(理论上它包含所有可能的信息),保存数据XXX的地址(极有可能)将与XXX本身一样大.

换句话说,信息不是保存在Pi本身的数字中,而是保存在信息开始的地址中.

Answer 2

因为我们在休息室里都很无聊,所以我继续进行搜索,找出特定长度的"消息"的平均偏移量.

我下载了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

Answer 3

不,不可能在随机序列中有效地找到任意序列 - 从"随机"的定义开始.(如果有办法预测序列发生的位置,那就不是随机的.)

至于索引所有位置,那么,你获得了什么？你实际上是说"跳转到起点0 ......"然后你必须说"......然后用π计算下一个JPEG大小的位......"(没有胜利,因为你必须使用准备计算的能量)或"......然后在mega-π指数中查找下一个JPEG大小的数据块." (在这种情况下,你可以,你知道,加载JPEG文件.)

你不能赢,你不能收支平衡(而且,为了它的价值,你无法摆脱游戏).

更新:@Mysticial的答案比我的好.他的观点

例如,如果有人拥有SSN:938-93-3556

它起始于Pi的597,507,393.这个数字597,507,393与SSN本身一样长.换句话说,我们通过使用Pi获得了什么.

优雅地捕捉到根本问题.

Answer 4

这种说法是错误的.Pi是无限的,它的下一个数字是不可预测的,但这并不意味着每个可能的字符串都在那里.

例如,假设我创建了一个类似于pi的函数,但是只要存在20个二进制零的序列,就计算接下来的20位,并用它替换零.

该序列也是无限的,并且是不可预测的 - 但我们可以肯定地知道它从不包含20个二进制零的序列.

无法证明PI包含所有可能的位序列.

这也可能有助于解答它:http: //www.youtube.com/watch？v = 8PUJvAlD64k