有限长度的二进制字符串是否能在合理时间内在圆周率π中找到？

Question

有限长度的二进制字符串是否能在合理时间内在圆周率π中找到？

algorithmcomplexity-theorycommunicationpi

30

所以，前段时间我读了一个笑话，大概是这样的：

“永远不要用二进制计算圆周率 - 因为它具有无限随机性，理论上包含每个有限位字符串。因此，你将拥有所有存在的受版权保护的资料，并且会面临一些严重的罚款。”

显然，这是为了幽默而写的，但它让我思考。如果在pi的二进制表示中存在每个有限的位字符串，是否可以使用这作为传输数据的方法？

例如，假设我想传输可以被解释为JPEG图像的位字符串。我不会直接发送信息，而是在pi的数字中找到其位置，然后只需发送在pi的数字中的第一个位的位置以及该字符串的长度即可。

对我来说，这似乎非常简单，但明显的障碍在于，在前数万亿个数字内找到这个字符串的概率极小。因此，可能需要花费巨大的时间才能找到。

我的想法是，可以专门用几台机器来搜索pi内的大文件，然后创建一个包含它们起始位置的索引。因此，每次计算只需发生一次，然后从那时起可以非常快速地传输该信息。

那么，您认为这有可能吗？还是这些计算需要太多时间？

感谢阅读！如果我忽略了任何发布准则，请您见谅，这是我在该论坛上的第一个问题。

编辑：

感谢您们的快速回复！我觉得我的推理存在错误，很高兴知道原因！

- Chris Staikos

3

已知的π的数字只有10万亿位，即10的13次方。在这些数字中很难找到任何超过13位长度的随机字符串。 - Mysticial

3

似乎您缺少一个重要的概念——“信息熵”。即使您有无限位数的圆周率，包含XXX数据的地址长度也至少与XXX本身一样长。 - Mysticial

2

@trumpetlicks 不管是二进制还是十进制都没关系。它们可以互相编码。这与信息熵有关。 - Mysticial

1

@trumpetlicks 我的意思是压缩不可能，因为地址会和数据本身一样大。 - Mysticial

2

@MooingDuck：是的和不是。在所有可能的输入字符串中，是的。但是人们关心的输入大多数包含一定程度的结构和冗余，而不是纯熵 - 在这种情况下，压缩不仅可能，而且通常效果很好。 - Jerry Coffin

显示剩余11条评论

5个回答

23

因为我们在 Lounge<C++> 中都有点无聊，所以我写了一个搜索来查找特定长度的“消息”的平均偏移量。

我下载了100万位圆周率数并查找了所有固定长度（例如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

请注意，当我们搜索的π的数字数量达到其数字数量的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和π的位数：https://gist.github.com/3062541

- sehe

9

基数是任意的。所有在十进制中它行不通的原因，在二进制中也完全一样，只不过你需要将所有的平均数乘以3.32192809。 - Mooing Duck

@trumpetlicks 澄清：3.32192809... ~= ln(10)/ln(2) - sehe

2

+1 因为无聊而尝试这个。我今天早上起得太早了，所以正在打盹。:P - Mysticial

@Mysticial，你在说什么“无聊到发慌”？+1赞同你的“超棒”。 - Drise

6

不可能在随机序列中高效地找到任意序列，这是“随机”的定义所决定的。（如果有办法预测序列出现的位置，那它就不是随机的了。）至于索引所有位置，你得到了什么？实际上你只是在说“跳转到起始点0...”，然后你必须说“...然后计算π中下一个JPEG大小的位...”（没有胜利，因为你必须耗费能量进行计算），或者“...然后在mega-π索引中查找下一个JPEG大小的数据块。”（这种情况下，你可以直接加载JPEG文件。）你赢不了，也无法打平（值得一提的是，你无法退出游戏）。

更新：@Mysticial的答案比我的更好。他的观点如下：

例如，如果某人拥有社会安全号码：938-93-3556 它在π中的偏移量为597,507,393。这个数字大约与SSN本身一样长。换句话说，我们使用π没有获得任何好处。

- Larry OBrien

2

有趣。这似乎集中在找到偏移量的可行性上。问题是，如果你忽略了它，你会遇到真正的问题：通过表示偏移量（而不是实际数据），你会失去信息效率。 - sehe

@Mysticial 是的，你的回答比我的好，我的只是一个随意的回应。 - Larry OBrien

"在一个随机序列中，要高效地找到一个任意的序列是不可能的" - 虽然这是真实的，但π并不是一个随机序列。例如，可以有效地计算π的第n位数字，而无需计算之前的数字。当然，一些数论家可能会想出一种有效的方法来定位pi中任意比特串的第一个位置... 但是（除了超出本网站范围之外），这并不能给我们提供一种压缩该比特串的方法，因为@Mystical提到的熵原因。 - BlueRaja - Danny Pflughoeft

实际上这是可能的。这就是DNA序列索引的做法。 - Erik Aronesty

5

那个说法是错误的。圆周率是无限的，它的下一位数字是不可预测的，但这并不意味着每一个可能的字符串都在其中。

例如，假设我创建了一个类似于圆周率的函数，但每当出现20个二进制零时，就计算接下来的20个位，并用它替换零。

那个序列也是无限的和不可预测的，但我们可以肯定地知道它从未包含过20个二进制零的序列。

没有办法证明圆周率包含每一个可能的位序列。

这可能也有助于回答： http://www.youtube.com/watch?v=8PUJvAlD64k

- Rafael Baptista

抱歉，但如果我们可以计算10^13位数字，并且原则上可以计算Pi的任何一位数字（在足够的时间/内存下），这些数字不能被描述为“不可预测”。然而，如果一个“随机”序列不包含某些固定字符串，则它不能被视为随机（关于图灵机；有几个定义，但它们在很大程度上是等效的）。 - jpalecek

它们是不可预测的，因为您无法在计算pi到某个数字之前预测第n个数字是什么。 - Rafael Baptista

1

实际上，有一种名为Spigot算法的方法可以计算pi的二进制位数，而无需计算前面的数字（BPP公式已经相当知名）。此外，我不确定您是如何得出我们无法证明pi包含每个可能的比特序列的结论（目前尚不清楚它是否包含）。 - Nabb

我并不是说我能证明它不存在。我只是说像圆周率这样的无限不重复伪随机数序列不能被证明拥有每个序列。 - Rafael Baptista

我同意@nabb的观点 - 说某件事情无法被证明是一个相当强烈的主张。 - Erik Aronesty

我该如何表达这一点，以便能够绕过你们数学专家呢？要不这样说：“具有无限非重复伪随机数序列的特性并不能保证该序列中存在每个可能的有限子序列。” 我在我的帖子中通过构造来证明这一点。 - Rafael Baptista

1

因为π是无限的且随机的，理论上包含了每一个有限的比特串。

π是无限的，但绝对不是随机的 - 即它的数字可以通过大小为O(log n)的程序计算出来（因此，比前缀小得多的程序就可以生成前缀），这意味着Pi前缀的Kolmogorov复杂度在渐近意义下小于它们的大小。因此，尚未证明它包含每个有限的字符串（我不知道）。

- jpalecek

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mysticial · Accepted Answer

在我的评论中进一步阐述。这里有一个非常重要的概念，叫做信息熵。

完全披露，我目前以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的数字中，而是保存在信息开始的地址中。