图灵机掷骰子吗？

September 3, 2020

图灵机掷骰子吗？

不会，而且也不需要。只要图灵机自己觉得结果像是随机的就行了。

这就是伪随机生成器定理。如果在理念上真的存在无法被鉴别的伪随机生成器，那么一则困扰人类百年的谜语也可以得到解答。

引子

What is the purpose of our defense policy?

To defend Britain.

No, Bernard. It is to make people BELIEVE Britain is defended

伪随机性

所谓伪随机性，就是某种分布和真随机实在太像了，以至于人们没法在多项式时间内找出该分布的纰漏。

令 $U$ 为一个含有若干0和1的真随机的均匀分布， $D\_{n}$ 为我们想要验证的含有分布， $C$ 为任意的多项式规模的布尔电路（可以理解为小于多项式的时间/空间复杂度的输出为0或1的算法）， $\varepsilon$ 为与 $n$ 相关的任意多项式的倒数，伪随机分布的严谨定义如下：

|\Pr_{x\subset U}[C(X)=1] - \Pr_{x\subset D}[C(X)=1]|\leq \varepsilon

从反面来说，如果我们能找到一个确定的多项式规模的算法，以足够大的优势鉴别出 $x$ 是从 $U$ 还是 $D\_{n}$ 中选出来的，那么我们就可以说这个分布也许欺骗不过图灵机。

e.g. 我们构造这样一个 $C(x)$ ，当 $x$ 中的0多余1时输出0，否则输出1。显然， $\Pr\_{x\subset U}[C(X)=1] = 0.5$ ，因为真正的均匀随机分布0和1的数量应当是相等的。如果一个分布中0总是以 $\varepsilon$ 的优势多于或是少于1，那么我们就可以说这个分布被 $C$ 所攻破了。

e.g. 我们假设 $D\_{n}$ 是一个由 RC4¹ 算法生成的一个序列，构造 $C(x)$ ，如果 $x$ 的第二个byte为0则输出0，否则输出1。由于RC4算法存在相当大的偏差，当随机数种子满足一定条件的时候，第二个byte将总是为0。因此，一个非常简单的 $C$ 就能够攻破在过去很受欢迎的RC4算法。

读到这里，也许你会觉得我们的要求似乎太高了，任意的 $C$ 都无法攻破才能证明一个分布的伪随机性。

伪随机生成器

我们常常利用图灵机来帮助生成“伪随机”序列，这样的算法就被成为伪随机生成器。伪随机生成器通常需要一个种子，来帮助生成一定长度的序列。假设种子的长度为 $l$ ，那么当我们能够生成 $l+1$ 位的“伪随机”序列时，我们就能够构造出生成任意多项式 $m = poly(l)$ 长度的序列的伪随机生成器。只要第 $l + 1$ 位足够严谨，那么所有 $m$ 位也都会足够严谨。

这点是可以得到严格证明的，详见尾注²。

我们有一个真正意义上的伪随机生成器吗？答案既不是有，也不是没有，而是不知道。我们既无法证明某一个完美的伪随机生成器存在，也无法证明它不存在。但是我们知道，如果它真的存在，那么我们不光会多了一个只会说没人能理解的胡话的算法，还能证明一个关于计算复杂性理论的百年之谜。

单向函数与伪随机生成器

单向函数 (One-way function)是一种这样的单射函数：对于每一个输入，函数值都（在多项式时间内）容易计算，但是给出一个函数值，算出原始输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。单向函数的存在与否和伪随机生成器有着千丝万缕的联系。

假设某一天，我们得到了一个真正的伪随机生成器 $G*{l}:\{0 ,1\}^{l} \rightarrow \{0 ,1\}^{2l}$ ，我们就可以用它构造这样一个函数 $ƒ: \{0 ,1\}^{l} \rightarrow \{0 ,1\}^{l}$ ，其只将 $G*{l}$ 的前半作为其输出，那么ƒ就是一个真正的单向函数。我们可以用反证法来进行证明：

我们先可以假设这样一个电路 $C$ 可以在多项式时间内找出ƒ的逆，那么 $\Pr[ ƒ(C(ƒ(x,y))) = ƒ(x,y) ] > \varepsilon$ ，那么C就能够用来鉴别 $G\_{l}$ 和 $U$ 的区别。因为 $C$ 只能以 $\frac{1}{2^{l}}$ 猜中一个真正的随机分布U，但是能够以 $\varepsilon$ 猜中x。两者之差无法被忽视。

因此，只要伪随机生成器存在，那么单向函数就存在。同时逆命题也是成立的，只不过证明的过程更加复杂³。

等等，P≠NP ？！！

是的，只要单向函数存在，那么P就不等于NP了。还是反证法，假设P=NP的话，那么找出一个单向函数的逆就和验证它的逆一样简单。只要代回到原函数就可以验证一个函数的逆，而原函数是可以在多项式时间内完成的计算，那么既然我们能在多项式时间验算它的逆，那么也可以在多项式时间找出所谓单向函数的逆。那么单向函数就不存在了！

那么

伪随机生成器的存在意味着单向函数的存在，同时也意味着P≠NP。
伪随机这个术语也和计算机科学这一术语一样糟糕，根据定义，真随机均匀分布具有伪随机性，因为我们当然无法分辨它和自己的区别。
直到量子物理，人所能认知到的随机只存在于抽象的概念中
我们大部分认为的随机，其实是非常糟糕的伪随机，是一个系统的复杂程度超出的人脑的认知时举起的白旗。