我刚读了一个有趣的问题,关于一个从不连续三次生成相同值的随机数生成器.这显然使随机数发生器与标准的均匀随机数发生器不同,但我不确定如何定量描述该发生器与不具有此属性的发生器的区别.
假设你递给我两个随机数生成器R和S,其中R是一个真正的随机数生成器,S是一个真正的随机数生成器,它被修改为永远不会连续三次生成相同的值.如果你没有告诉我哪一个是R或S,我能想到的唯一方法就是运行生成器,直到其中一个生成器连续三次产生相同的值.
我的问题是 - 是否有一个更好的算法来告诉两个发电机分开？不产生相同数字三次的限制是否会以某种方式影响发电机的可观察行为,而不是阻止三个相同的值连续出现？
根据赖斯定理，我们无法区分哪个是哪个。
证明：设 L 为正常 RNG 的输出。令 L' 为 L，但删除所有长度 >= 3 的序列。有些 TM 可以识别 L'，但有些则不能。因此，根据莱斯定理，确定 TM 是否接受 L' 是不可判定的。
正如其他人所指出的，您也许可以做出“它已经运行了 N 个步骤而没有重复 3 次”之类的断言，但您永远不能跳跃到“它永远不会重复一个数字 3 次”。更恰当地说，至少存在一台机器，您无法确定它是否满足此标准。
警告：如果您有一个真正的随机生成器（例如核衰变），那么赖斯定理可能不适用。我的直觉是该定理对于这些机器仍然成立，但我从未听说过它的讨论。
编辑：二次证明。假设P(X)以高概率确定是否X接受L'。我们可以构造一个（无限多个）程序 F，如下所示：
F(x): if x(F), then don't accept L'
else, accept L'
P 无法确定 的行为F(P)。此外，sayP正确预测了 的行为G。我们可以构建：
F'(x): if x(F'), then don't accept L'
else, run G(x)
因此，对于每一个好的案例，都必须存在至少一个坏的案例。