更改
跳到导航
跳到搜索
第80行：
第80行： − 下面的+ − 篇幅+ − 我们+ − 将+ − 具 − 体 − 讨 − 论 − 我们的“方格宇宙”的 − 细节性质 − 和 − 规律 − 。实 − 际 − 上， − “方格宇 − 宙”有一个学 − 名叫作 − “ − 细胞 − 自动机” − 或者 − “ − 元胞 − 自动机”， − 英文 − 名 − 字是“ − Cellular Automata − ”， − 下面的 − 讨 − 论 − 中，“方格宇宙”和“ − 细胞 − 自动机”这 − 两 − 个 − 名 − 字我 − 将混 − 合 − 使 − 用，你要 − 知道 − 这 − 两 − 个 − 指同一个 − 东西 − 就可以了。 − 一 − 般 − 的，一个 − 细胞 − 自动机是由这几个要 − 素 − 构成的： − 细胞 − 、 − 细胞空 − 间、 − 邻 − 居、 − 规则 − 。下面 − 分别 − 叙述 − 。 − 在+ − 细胞+ − 自动机中，一个小格子就是一个+ − 细胞+ − 。在大楼霓虹灯动画中的窗户就是一个+ − 细胞 − 。 − 细胞 − 具 − 有 − 状态 − ，比如大楼霓虹灯中每个窗户的开灯还是关灯就是 − 细胞 − 的 − 状态 − 。我们把每一个 − 细胞 − 的 − 所 − 有可 − 能状态 − 的集合 − 叫做 − 细胞 − 的 − 状态 − 集。在大楼霓虹灯中每个窗户有开灯关灯 − 两 − 个 − 状 − 态 − ，我们可以用集合的 − 符号 − 表示为 − − − − ，因 − 此 − 这是一个 − 两状态 − 的集合。 − 更 − 一 − 般 − 的， − 一个 − 细胞 − 可 − 能 − 有 − n − 种 − 状态 − 。 − 每一个 − 状态 − 都可以给他 − 赋予 − 不同的 − 含义 − ，比如在“ − 生命 − 游戏”中，我们可以用 − 状态 − 集 − − ， − 1} − 表示一个 − 细胞 − 的 − 状态 − 。也可以用 − − − − − − 表示一个 − 细胞 − （ − 生命 − 体）的 − 状态 − ，当然也可以用 − − 开 − 灯，关灯 − − 表示 − 运 − 行在大楼霓虹灯上的“ − 生命 − 游戏”这个 − 软件 − 。 − 对于 − 有 − n − 个 − 状态 − 的 − 细胞 − 自动 − 机，我们不妨把这 − n − 种 − 状态 − 想 − 象 − 成 − n − 种不同的颜色，这 − 毫 − 不 − 影响 − 我们 − 对 − n − 状态 − 细胞 − 自动机的 − 理 − 解 − 。仍然用大楼霓虹灯 − 做 − 比 − 喻 − ，如果每个窗户 − 后 − 面的灯是有颜色的，比如有 − 红 − 、 − 蓝 − 两 − 种颜 − 色，那么每个窗户就有 − − 红 − 色灯， − 蓝 − 色灯，关灯 − − 三种 − 状态 − 。当然我们也可以把关灯 − 理 − 解 − 为黑 − 颜色灯的 − 状态 − ， − 所 − 以这和用 − − 红 − 灯， − 蓝 − 灯，黑灯 − − 的表示是一样的。 − 简单+ − 地+ − 说+ − 细胞 − 自动机中 − 细胞 − 分 − 布 − 的 − 空 − 间就是 − 细胞空 − 间。在“ − 生命 − 游戏”中， − 细胞空 − 间就 − 是一个二 − 维 − 的大方 − 块 − ，并且 − 所 − 有的 − 细胞 − 都是以 − 水 − 平 − 和 − 竖直 − 两 − 个方 − 向 − 整齐排列的。关 − 于 − 细胞空 − 间有以下几个 − 概念 − 也就是+ − 细胞空+ − 间的+ − 维+ − 度+ − 。+ − 常见+ − 的+ − 细胞空+ − 间都是一+ − 维+ − 或者 − 二 − 维 − 的，一 − 维 − 的 − 细胞空 − 间就是在 − 一 − 条 − 直线 − 上的方格，如下图： − <gallery> − − </gallery> − 二 − 维 − 的 − 细胞空 − 间就是一个 − 平 − 面，我们 − 前 − 面 − 介绍 − 的“ − 生命 − 游戏”就是一个二 − 维 − 的 − 细胞空 − 间。 − 三 − 维 − 的 − 细胞空 − 间是一个 − 立 − 体的 − 立 − 方体，下面给出了示意： − <gallery> − − </gallery> − 当然我们还可以给出 − 4 − 维细胞空 − 间、 − 5 − 维细胞空 − 间 − 等等 − ， − 但 − 那已经 − 远远超 − 出了图 − 形 − 表 − 达 − 的 − 能力 − 极限 − 了。 − 细胞+ − 的+ − 形状+ − 以+ − 及+ − 细胞+ − 之间的排列方+ − 式 − 。我 − 们 − 常见 − 的是 − 横 − 平 − 竖直 − 的 − 四 − 方格排列方 − 式 − ，当 − 然 − 还可以有其他的几 − 何 − 划 − 分 − ，如下面的几个 − 例 − 子： − <gallery> − − </gallery> − 这些几 − 何 − 划 − 分分别 − 是三 − 角 − 构 − 形 − ， − 四 − 方构 − 形 − 和 − 四 − 方 − 网 − 格还有 − 六 − 边形网 − 格。 − 一 − 般 − 的， − 只要 − 某 − 种图 − 形能够形 − 成 − 对 − 一个 − 平 − 面 − 区域 − 的 − 覆盖 − 就可以 − 认 − 为是一种 − 细胞空 − 间的几 − 何 − 划 − 分 − 。 − 细胞空+ − 间+ − 边+ − 界+ − 处+ − 细胞 − 的 − 处理 − 方法。 − 无论 − 是 − 哪 − 一种 − 细胞空 − 间， − 为了 − 能 − 在 − 计算 − 机上 − 进 − 行 − 模 − 拟 − 它都 − 必须 − 是一个有 − 限 − 的 − 区域 − ，因 − 此 − 我们 − 必须 − 考虑 − 在 − 边 − 界 − 上的 − 细胞空 − 间 − 处理 − 方法。 − 比如在 − “ − 生 − 命 − 游戏” − 中， − 它的 − 空 − 间是一个方 − 块 − ， − 那么在方 − 块 − 四 − 个 − 边 − 上的 − 细胞 − 应该如 − 何处理 − 呢？要 − 知道 − 左 − 边 − 的方格没有 − 更左边 − 的 − 邻 − 居了。 − 一种很自然的想法就是把 − 最 − 右边边 − 界 − 处 − 的 − 细胞 − 当 − 作 − 是这个 − 细 − 胞 − 的 − 左邻 − 居， − 而 − 右边边 − 界 − 处 − 的那个 − 细胞 − 的 − 右邻 − 居是该 − 细胞 − 。 − 也就是 − 说 − 细胞空 − 间的 − 左右两端被 − 连接 − 在了一起，就好像是一个 − 圆柱 − 面。同样的方法也可以应用到上下 − 两 − 个 − 边 − 界 − 上。 − 在 − 细胞 − 自动机的实 − 际 − 应用中， − 还可以用反 − 射 − 型 − 、 − 固 − 定 − 值 − 型 − 的方法 − 处理边 − 界 − 这里不 − 再 − 多 − 说 − 了。 − 细胞+ − 自动机的+ − 运+ − 行+ − 规律+ − 不+ − 仅仅取+ − 决于某+ − 一个+ − 细胞+ − 自+ − 身 − 的 − 状态 − ， − 而且也 − 取 − 决于 − 它 − 周围 − 的多 − 个 − 细胞 − 的 − 状态 − ，这些 − 细胞 − 就是该 − 细胞 − 的 − 邻 − 居。我们可以 − 采 − 用多种方法定 − 义 − 一个 − 细胞 − 的 − 邻 − 居。 − 在方格 − 细胞空 − 间中， − 常 − 用的 − 邻 − 居类 − 型包括 − 下面几种： − <gallery> − − </gallery> − 这其中， − 黑色的方格表示当 − 前 − 的 − 细胞 − ， − 灰色的表示它的 − 邻 − 居。 − 上面的三种类 − 型 − 都是人们 − 常 − 用的类 − 型 − 。在 − 实 − 际 − 应用中， − 还有很多 − 邻 − 居的类 − 型 − 。 − 另外 − ， − 邻 − 居的类 − 型 − 也 − 跟细胞空 − 间的几 − 何 − 划 − 分 − 和 − 维 − 度 − 有关系。 − 在一 − 维 − 的 − 细胞 − 自动机中， − 我们 − 常常 − 用一个 − 细胞 − 在一个方 − 向相 − 邻 − 的 − 细胞 − 个 − 数 − 定为该 − 细胞 − 自动机的 − 邻 − 居 − 半径 − ， − 比如 − 邻 − 居 − 半径 − 为 − 1 − 的一 − 维细 − 胞 − 自动机的 − 邻 − 居 − 区域 − 如下图示 − <gallery> − − − </gallery> + − 正如在第一+ − 节+ − 中+ − 叙述 − 的， − 要想 − 产生 − 动 − 态 − 的过 − 程 − ，每 − 个 − 细胞 − 都需要 − 遵循 − 一些 − 规则 − 改 − 变自 − 身 − 的 − 状态 − 。 − 这些 − 规则 − 就好比是一些指令指 − 导 − 着每个 − 细胞 − 根据 − 它自 − 身 − 的 − 状态 − 和它 − 周围 − 邻 − 居的 − 状态 − 不断的 − 改 − 变自 − 身 − 。我们也可以把每一 − 条规则 − 看成是一个机 − 器 − f − 。它的 − 作 − 用是把当 − 前 − 方格 − t − 时 − 刻的 − 状态 − 和他的 − 邻 − 居在 − t − 时刻的 − 状态 − 转 − 换成 − t+ − 1 − 时刻该方格的 − 状态 − 。如果用 − s − t+ − 1 − 表示 − 在 − t+1 − 时刻该 − 细胞 − 的 − 状态 − ，而用 − N − t − 表示 − t − 时刻 − 细胞 − 邻 − 居 − 区域 − 内 − 所 − 有 − 细胞 − 的 − 状态 − （ − 包括 − 这个 − 细胞 − 自 − 身 − 在 − t − 时刻的 − 状态 − ） − ，那么 − 利 − 用 − 规则 − 函 − 数 − f − ，我们可以得到下面的关系 − 式 − ： − s − − − − − 。 − 或者 − ， − 我们把 − 细胞 − 自动机的 − 规则 − 看成是一个魔术 − 箱 − 子， − 输入 − 给它的是 − 邻 − 居 − 区域 − 所 − 有 − 细胞 − 的 − 状态 − N − − ， − 输 − 出的是这个 − 细胞 − 的下一时刻的 − 状态 − s − − 。用下图表示： − 比如+ − “+ − 生命+ − 游戏”+ − 中，+ − 某+ − 个+ − 细胞核 − 它的 − 八 − 个 − 邻 − 居在 − 某 − 一时刻 − t − 分别处于状态 − 0 − （自己 − ） − − （ − 左 − 上） − − （上 − ） − − （ − 右 − 上） − − （ − 右 − ） − − （ − 右 − 下） − − （下 − ） − − （ − 左 − 下） − − （ − 左 − ） − 。这样 − N − − 可以 − 看 − 作 − 是一列： − − − − − − − − ， − 根据 − “ − 生命 − 游戏” − 的 − 规则 − 2 − ， − 那么在 − t+ − 1 − 的 − 状态 − 就 − 应该是 − s − − − − 。 − 也就是 − 说 − s − − − − − 。 − 由 − 所 − 有的 − 规则 − 组成的集合我们就 − 叫做规则 − 集。 − 比如在 − 生命 − 游戏中， − 规则 − 1 − 和 − 规则 − 2 − 构成 − 的集合就是一个 − 规则 − 集。 − 这里可 − 能 − 会有一个问题， − 万 − 一 − 某 − 一种 − 输入 − 状态 − 找 − 不到 − 对 − 应的 − 规则 − 怎 − 么 − 办 − 呢？比如在我们的 − 生命 − 游戏的 − 规则 − 集合中，如果 − 仅仅 − 有 − 规则 − 1 − ，而没有 − 规则 − 2 − 。这样当 − 某 − 个窗户 − 后 − 的朋友关灯的 − 情况 − 下就不 − 知道 − 下一时刻到 − 底 − 是开灯还是关灯了。 − 因为 − 规则 − 1 − 仅仅 − 定 − 义 − 了如果当 − 前 − 窗户是开灯的 − 情况 − 下该如 − 何 − 转 − 移 − 到下一个 − 状态 − ， − 而 − 对于 − 当 − 前 − 窗户关灯的 − 情况 − 没有定 − 义 − 。 − 显 − 然， − 如果出现这种 − 情况 − 我们的游戏就不 − 能 − 玩下 − 去 − 了。 − 因 − 此 − ，关 − 于规则 − 的集合 − 我 − 们 − 必须 − 有下面的要 − 求 − ： − 规则 − 集要 − 能对所 − 有可 − 能 − 的 − 输入 − 状态 − 组合 − （当 − 前 − 邻 − 居 − 区域 − 中的 − 细胞 − 状态 − 的 − 所 − 有可 − 能 − 组合）都有 − 相 − 应的 − 处理 − 。 − 到这里， − 我们已经 − 介绍 − 了一个一 − 般 − 的 − 细胞 − 自动机的 − 基本 − 要 − 素 − ，可 − 以 − 说 − 这些 − 基本 − 要 − 素 − 在不 − 同的 − 情况 − 下会 − 造 − 就 − 完全 − 不同的“方 − 格宇宙” − 。 − 接 − 下来的问题 − 自然是，由 − 这些要 − 素 − 到 − 底 − 能 − 得到 − 什么样的 − “方格宇宙” − 呢？以 − 及 − 得到的这些 − “方格宇宙” − 会有什么样的 − “ − 物 − 理规律 − ” − 呢？我 − 们下面就 − 从 − 一 − 维 − 的 − 细胞 − 自动机开 − 始 − 探索 − “方格宇宙”的“ − 物 − 理规律 − ” − 。
→细胞自动机
== 细胞自动机 ==
== 细胞自动机 ==
下面的篇幅我们将具体讨论我们的“方格宇宙”的细节性质和规律。实际上，“方格宇宙”有一个学名叫作“细胞自动机”或者“元胞自动机”，英文名字是“Cellular Automata”，下面的讨论中，“方格宇宙”和“细胞自动机”这两个名字我将混合使用，你要知道这两个指同一个东西就可以了。
一般的，一个细胞自动机是由这几个要素构成的：细胞、细胞空间、邻居、规则。下面分别叙述。
=== 细胞 ===
=== 细胞 ===
在细胞自动机中，一个小格子就是一个细胞。在大楼霓虹灯动画中的窗户就是一个细胞。细胞具有状态，比如大楼霓虹灯中每个窗户的开灯还是关灯就是细胞的状态。我们把每一个细胞的所有可能状态的集合叫做细胞的状态集。在大楼霓虹灯中每个窗户有开灯关灯两个状态，我们可以用集合的符号表示为{开灯，关灯}，因此这是一个两状态的集合。更一般的，一个细胞可能有n种状态。
每一个状态都可以给他赋予不同的含义，比如在“生命游戏”中，我们可以用状态集{0，1}表示一个细胞的状态。也可以用{生,死}表示一个细胞（生命体）的状态，当然也可以用{开灯，关灯}表示运行在大楼霓虹灯上的“生命游戏”这个软件。对于有n个状态的细胞自动机，我们不妨把这n种状态想象成n种不同的颜色，这毫不影响我们对n状态细胞自动机的理解。仍然用大楼霓虹灯做比喻，如果每个窗户后面的灯是有颜色的，比如有红、蓝两种颜色，那么每个窗户就有{红色灯，蓝色灯，关灯}三种状态。当然我们也可以把关灯理解为黑颜色灯的状态，所以这和用{红灯，蓝灯，黑灯}的表示是一样的。
{
开灯，关灯
}
{0
{
生
,
死
}
{
}
{
}
{
}
=== 细胞空间 ===
=== 细胞空间 ===
简单地说细胞自动机中细胞分布的空间就是细胞空间。在“生命游戏”中，细胞空间就是一个二维的大方块，并且所有的细胞都是以水平和竖直两个方向整齐排列的。关于细胞空间有以下几个概念
==== 维度 ====
==== 维度 ====
也就是细胞空间的维度。常见的细胞空间都是一维或者二维的，一维的细胞空间就是在一条直线上的方格，如下图：
[[File:屏幕快照 2015-12-11 23.16.31.png|屏幕快照 2015-12-11 23.16.31.png]]
二维的细胞空间就是一个平面，我们前面介绍的“生命游戏”就是一个二维的细胞空间。三维的细胞空间是一个立体的立方体，下面给出了示意：
[[File:屏幕快照 2015-12-11 23.17.26.png|屏幕快照 2015-12-11 23.17.26.png]]
当然我们还可以给出4维细胞空间、5维细胞空间等等，但那已经远远超出了图形表达的能力极限了。
File:屏幕快照 2015-12-11 23.16.31.png|
File:屏幕快照 2015-12-11 23.17.26.png|
==== 细胞空间的几何划分 ====
==== 细胞空间的几何划分 ====
细胞的形状以及细胞之间的排列方式。我们常见的是横平竖直的四方格排列方式，当然还可以有其他的几何划分，如下面的几个例子：
[[File:屏幕快照 2015-12-11 23.19.14.png|屏幕快照 2015-12-11 23.19.14.png]]
这些几何划分分别是三角构形，四方构形和四方网格还有六边形网格。一般的，只要某种图形能够形成对一个平面区域的覆盖就可以认为是一种细胞空间的几何划分。
File:屏幕快照 2015-12-11 23.19.14.png|
==== 边界处理方法 ====
==== 边界处理方法 ====
细胞空间边界处细胞的处理方法。无论是哪一种细胞空间，为了能在计算机上进行模拟它都必须是一个有限的区域，因此我们必须考虑在边界上的细胞空间处理方法。比如在“生命游戏”中，它的空间是一个方块，那么在方块四个边上的细胞应该如何处理呢？要知道左边的方格没有更左边的邻居了。一种很自然的想法就是把最右边边界处的细胞当作是这个细胞的左邻居，而右边边界处的那个细胞的右邻居是该细胞。也就是说细胞空间的左右两端被连接在了一起，就好像是一个圆柱面。同样的方法也可以应用到上下两个边界上。
在细胞自动机的实际应用中，还可以用反射型、固定值型的方法处理边界这里不再多说了。
=== 邻居 ===
=== 邻居 ===
细胞自动机的运行规律不仅仅取决于某一个细胞自身的状态，而且也取决于它周围的多个细胞的状态，这些细胞就是该细胞的邻居。我们可以采用多种方法定义一个细胞的邻居。在方格细胞空间中，常用的邻居类型包括下面几种：
[[File:屏幕快照 2015-12-11 23.21.38.png|屏幕快照 2015-12-11 23.21.38.png]]
这其中，黑色的方格表示当前的细胞，灰色的表示它的邻居。上面的三种类型都是人们常用的类型。在实际应用中，还有很多邻居的类型。另外，邻居的类型也跟细胞空间的几何划分和维度有关系。在一维的细胞自动机中，我们常常用一个细胞在一个方向相邻的细胞个数定为该细胞自动机的邻居半径，比如邻居半径为1的一维细胞自动机的邻居区域如下图示:
[[File:屏幕快照 2015-12-11 23.23.18.png|屏幕快照 2015-12-11 23.23.18.png]]
[[File:屏幕快照 2015-12-11 23.23.35.png|邻居半径为2的一维细胞自动机的邻居区域如下图示]]
File:屏幕快照 2015-12-11 23.21.38.png|
File:屏幕快照 2015-12-11 23.23.18.png|
File:屏幕快照 2015-12-11 23.23.35.png|邻居半径为2的一维细胞自动机的邻居区域如下图示
一个细胞和它的邻居一起的空间区域被叫做邻居空间或者邻居模板
一个细胞和它的邻居一起的空间区域被叫做邻居空间或者邻居模板
=== 规则 ===
=== 规则 ===
正如在第一节中叙述的，要想产生动态的过程，每个细胞都需要遵循一些规则改变自身的状态。这些规则就好比是一些指令指导着每个细胞根据它自身的状态和它周围邻居的状态不断的改变自身。我们也可以把每一条规则看成是一个机器f。它的作用是把当前方格t时刻的状态和他的邻居在t时刻的状态转换成t+1时刻该方格的状态。如果用st+1表示在t+1时刻该细胞的状态，而用Nt表示t时刻细胞邻居区域内所有细胞的状态（包括这个细胞自身在t时刻的状态），那么利用规则函数f，我们可以得到下面的关系式：s<sub>t+1</sub>=f(N<sub>t</sub>)。或者，我们把细胞自动机的规则看成是一个魔术箱子，输入给它的是邻居区域所有细胞的状态N<sub>t</sub>，输出的是这个细胞的下一时刻的状态s<sub>t+1</sub>。用下图表示：
t+1
=f(N
t
)
t
t+1
<gallery>
<gallery>
File:屏幕快照 2015-12-11 23.30.43.png|
File:屏幕快照 2015-12-11 23.30.43.png|
</gallery>
</gallery>
比如“生命游戏”中，某个细胞核它的八个邻居在某一时刻t分别处于状态0（自己）,1（左上）,1（上）,0（右上）,1（右）,0（右下）,0（下）,0（左下）,0（左）。这样N<sub>t</sub>可以看作是一列：(0,1,1,0,1,0,0,0,0)，根据“生命游戏”的规则2，那么在t+1的状态就应该是s<sub>t+1</sub>=1。也就是说s<sub>t+1</sub>=f(N<sub>t</sub>)=f(0,1,1,0,1,0,0,0,0)=1。
由所有的规则组成的集合我们就叫做规则集。比如在生命游戏中，规则1和规则2构成的集合就是一个规则集。这里可能会有一个问题，万一某一种输入状态找不到对应的规则怎么办呢？比如在我们的生命游戏的规则集合中，如果仅仅有规则1，而没有规则2。这样当某个窗户后的朋友关灯的情况下就不知道下一时刻到底是开灯还是关灯了。因为规则1仅仅定义了如果当前窗户是开灯的情况下该如何转移到下一个状态，而对于当前窗户关灯的情况没有定义。显然，如果出现这种情况我们的游戏就不能玩下去了。因此，关于规则的集合我们必须有下面的要求：规则集要能对所有可能的输入状态组合（当前邻居区域中的细胞状态的所有可能组合）都有相应的处理。
到这里，我们已经介绍了一个一般的细胞自动机的基本要素，可以说这些基本要素在不同的情况下会造就完全不同的“方格宇宙”。接下来的问题自然是，由这些要素到底能得到什么样的“方格宇宙”呢？以及得到的这些“方格宇宙”会有什么样的“物理规律”呢？我们下面就从一维的细胞自动机开始探索“方格宇宙”的“物理规律”。
,1
,1
,0
,1
,0
,0
,0
,0
t
(0,1,
1
,0,1,0,
0
,
0
,0)
t+
1
=1
t+1
=f(N
t
)=f(0,1,1,0,1,0,0,0,0)=1
== 解刨“方格宇宙” ==
== 解刨“方格宇宙” ==
=== 最简“方格宇宙” ===
=== 最简“方格宇宙” ===