Get best of the week

使用元胞自动机生成伪随机数：规则30

伪随机数生成器确定性地给出数字，但通常此类数字看起来是非周期性的（随机）。至少在大多数情况下，通常会使用此类数字。生成器获取一个初始值（理想情况下是一个真实的随机数）并生成一个数字序列，该序列是初始值和（或）序列中先前数字的函数。这样的数字是伪随机数（不是真正的随机数），这是由于以下事实：如果已知传输给生成器的初始值，则可以通过算法再次生成这些数字。真正的随机数是使用特殊的硬件或某些物理现象生成的-血液量的脉冲波动，大气压力，热噪声，量子过程等。



有许多方法可以生成伪随机数。例如，Blum – Blum – Shub算法，均方方法，带延迟的Fibonacci方法。今天，我们将讨论使用规则30生成随机数，该规则使用一种含糊的方法，其中涉及使用元胞自动机模型。该方法通过了许多标准随机数测试，并在Mathematica中用于生成随机整数。

元胞自动机


在讨论规则30的主题之前，让我们花一些时间进行细胞自动机研究。元胞自动机是一个离散模型，由任何尺寸的规则单元格组成。每个晶格单元可以处于一组有限的状态中。此外，对于每个小区，定义了诸如“邻居”的概念。例如，在某个小区附近，可以进入距离它不超过2的所有小区。有规则确定细胞之间如何相互作用以及如何进入下一代（状态）。这些规则主要由数学（可编程）函数表示，这些函数取决于单元格的当前状态及其相邻单元的状态。


元胞自动机的

描述上图中的元胞自动机的描述使您可以发现每个单元格可以处于两种最终状态之一0（红色显示）和1（黑色显示）。每个单元进入下一代，并采用将操作XOR应用于其8个邻居的状态。晶格的第一代（初始状态）是随机设置的。该细胞自动机的操作如下所示。


基于XOR的

细胞自动机的作用在1940年代，斯坦尼斯拉夫·乌兰（ Stanislav Ulam）和约翰·冯·诺伊曼（John von Neumann）提出了细胞自动机的思想。细胞自动机已在计算机科学，数学，物理学，复杂系统理论，理论生物学以及对介质和材料的微观结构进行建模的问题中得到应用。在1980年代，斯蒂芬·沃尔夫拉姆（ Stephen Wolfram）对规则30所基于的一维元胞自动机（也称为基本元胞自动机）进行了系统研究。

规则30


规则30是基本的（一维）细胞自动机，其中每个单元可以处于以下两种最终状态之一0（下图中的红色单元）和1（黑色单元）。单元格的附近由位于其左侧和右侧的两个最接近的邻居表示。单元的下一个状态（生成）取决于其当前状态及其邻居的状态。下图显示了将单元格转换到下一个状态的规则。


规则30

这些过渡到单元新状态的规则可以简化为left XOR (central OR right)。

我们以二维晶格的形式输出自动机的像元，其每一行代表一个世代（状态）。当计算出下一代细胞（状态）时，它会显示在最后一个已知状态的下方。每行包含有限数量的单元格，最后，这些单元格为“循环”。


规则30的作用

当一个单元格处于状态1（黑色）而其周围的所有单元格都处于状态0（红色）时，上述模式源自初始状态（第0行）。根据上述规则，计算出下一代细胞的状态（第1行）。垂直网格表示时间，行和列的交点表示系统开发特定阶段特定单元的状态。


t世代和t +1世代

随着图案的发展，通常会出现不同大小的红色三角形，但通常，在所得结构中无法识别出可区分的图案。晶格的上述片段是在任意选择的时刻制作的。在这里您可以看到混乱和非周期性。此属性是规则30，用于生成伪随机数。

伪随机数生成


如前所述，规则30显示了非周期性和混乱行为。结果，其应用导致根据简单且定义明确的规则创建复杂的，似乎是随机的模式。为了使用规则30生成随机数，使用中央晶格列，从中选择一个n随机位序列，从中生成所需的n位随机数。使用n列中的以下位生成下一个随机数。


使用规则30生成随机数

如果始终总是从第一行开始选择单元格，则生成的数字序列将始终是可预测的。这不是我们所需要的。为了创建伪随机数，我们将使用一个随机初始值（例如当前时间），跳过相应的行数，然后从n行中选择序列并基于它们创建随机数。

使用规则30生成的伪随机数在密码上不是安全的，但它们适用于模拟-直到我们使用不适当的初始值（例如）0。

应用规则30生成伪随机数的主要优点之一是，可以通过随机选择许多长度为n位的列以并行模式创建许多随机数。下面是通过使用初始值，此方法产生的8位数字的伪随机序列的一个例子0：220，197，147，174，117，97，149，171，240，241。

此外，初始值可用于设置模型的初始状态（0号线）。结果，只需选择即可获得伪随机数n从中心行开始，从零行开始。这种方法更有效，但高度依赖于初始值的质量。错误选择的初始值可能会导致出现预测正确的数字。这种方法的演示可以发现这里。

现实世界中的规则30


在自然界中可以看到规则30，其形式为腹足动物种类Conus纺织品的外壳上的图案。剑桥北火车站的框框描绘了使用Rule 30构建的模型的演化结果。

摘要


如果您发现规则30有趣，建议您使用p5库编写自己的仿真。可以以相当通用的形式实现此算法，这将允许同一程序为90、110、117等不同规则生成模式。使用各种规则生成的模式非常有趣。如果需要，可以进入下一个级别。您可以将模型扩展到三个维度，并探索模式的演变。我认为，如果编程具有视觉组件，可以带来很多乐趣。

当两个看似无关的科学领域，细胞自动机和密码学相结合，创造出令人惊讶的东西时，这真是令人惊讶。尽管这里描述的算法由于更有效的算法的出现而不再被广泛使用，但它鼓励我们创造性地使用元胞自动机。

亲爱的读者们！您使用什么伪随机数生成器？

More articles:


All Articles