更改
跳到导航
跳到搜索
第186行：
第186行： − 显+ − 然，+ − 对于+ − 最+ − 简单的一类+ − 细胞+ − 自动机，+ − 任+ − 何+ − 一组+ − 规则 − 的 − 输入 − 都是上表 − 所 − 列的 − 8 − 种 − 情况 − ， − 而不同的 − 仅仅 − 是 − 输 − 出 − 部分 − 。 − 我们把第一个 − 规则 − 集的 − 输 − 出 − 部分 − 写 − 成： − 00 − 1 − 1 − 01 − 01 − ，第 − 二 − 组 − 规则 − 集 − 的 − 输 − 出 − 部分 − 写 − 成： − 0 − 111 − 0 − 1 − 1 − 0 − ， − 显 − 然这 − 两 − 个 − 输 − 出不同， − 但 − 它们都是一个 − 长度 − 为 − 8 − 的二 − 进 − 制字 − 符 − 串 − 。 − 我们可以断 − 言 − 任 − 何 − 一个 − 长度 − 为 − 8 − 的二 − 进 − 制 − 串 − 都应该 − 对 − 应一组 − 规则 − 。 − 反过来 − 讲 − ， − 所 − 有可 − 能 − 的 − 规则 − 集都 − 能 − 写 − 为 − 长度 − 为 − 8 − 的二 − 进 − 制 − 串 − ，这一 − 共 − 有 − 2 − 8 − − 种可 − 能 − ，也就是 − 说规则 − 集一 − 共仅 − 有 − 25 − 6 − 个。 − 我们 − 知道 − ， − 任 − 意一个二 − 进 − 制 − 串 − 都 − 对 − 应一个十 − 进 − 制的 − 数 − 字，比如 − 0 − 0 − 1 − 1 − 01 − 01 − 对 − 应的 − 十 − 进 − 制 − 数 − 是 − 53 − 。 − 所 − 以， − 采 − 用这种用 − 10 − 进 − 制 − 数 − 字编 − 码 − 的二 − 进 − 制 − 串 − 方法， − 我们就把 − 规则 − 集 − 进 − 行 − 编 − 码 − 。 − 这种编 − 码 − 的方法很有 − 效 − ，因 − 为 − 任 − 何 − 细胞 − 自动机的 − 规则 − 都 − 逃 − 不出这 − 套 − 编 − 码 − 方案， − 但 − 是下 − 面我们 − 将 − 看到这种方法有些麻烦， − 所 − 以我们还 − 常常使 − 用 − 另外 − 一 − 套 − 编 − 码 − 的方法。 − 如果 − 细胞 − 自动机的 − 邻 − 居 − 半径 − 不是 − 1 − ， − 那么上 − 述 − 编 − 码 − 方案的 − 长度 − 将 − 会 − 急剧增加 − 。 − 例 − 如一个 − 邻 − 居 − 半径 − 为 − 2 − 的 − 细胞 − 自动 − 机的 − 所 − 有可 − 能 − 输入 − 就是 − 2 − 5 − − 种， − 因 − 而 − 根据 − 上面的 − 原理 − ， − 我们的编 − 码 − 也需要 − 32 − 位长 − ，这 − 显 − 然不实 − 际 − 了， − 因 − 此 − 我们应该 − 能 − 简 − 化 − 该编 − 码 − 方案。 − 考虑 − 这样的 − 规则 − 集， − 其中每一 − 条规则 − 的 − 输入 − 都 − 仅仅 − 考虑邻 − 居 − 区域 − 的 − 状态数值 − 之和。 − 比如在 − 最 − 简 − 细胞 − 自动机中， − 某 − 细胞 − 的 − 邻 − 居 − 区域 − 的三个 − 细胞 − 状态 − 是 − 01 − 1 − ， − 则 − 0+ − − − ，这样 − 输入 − 就是 − 2 − 。如 − 果是 − 01 − 0 − 呢， − 那 − 么 − 0+ − − − 1 − ，该 − 输入 − 就是 − 1 − 。这 − 样 − 所 − 有的 − 输入 − 可 − 能 − 仅仅 − 有 − 4 − 个 − 包括 − 0, − − − 3 − 。 − 我们把 − 所 − 有的 − 输 − 入 − 列出， − 按照 − 类似上面的方法就给每个 − 输入 − 指定 − 输 − 出的 − 状态 − 就得到了该编 − 码 − 。 − 比如一 − 条规则 − 的 − 输入输 − 出 − 对 − 应如下： − <gallery> − − − </gallery> − 把 − 1001 − 也就 − 是 − 9 − 作 − 为该 − 细胞 − 自动集的编 − 码 − 。当 − 邻 − 居 − 半径增 − 大到 − 2 − 的时候， − 所 − 有可 − 能 − 的 − 输入 − 是 − 5 − 个， − 所 − 以编 − 码 − 长度 − 是 − 5 − ， − 显 − 然比 − 刚才 − 简 − 化 − 多了。因而这种编 − 码 − 方案为 − 短 − 编 − 码 − 方案。
→“方格宇宙”的编码
=== “方格宇宙”的编码 ===
=== “方格宇宙”的编码 ===
显然，对于最简单的一类细胞自动机，任何一组规则的输入都是上表所列的8种情况，而不同的仅仅是输出部分。我们把第一个规则集的输出部分写成：00110101，第二组规则集的输出部分写成：01110110，显然这两个输出不同，但它们都是一个长度为8的二进制字符串。我们可以断言任何一个长度为8的二进制串都应该对应一组规则。反过来讲，所有可能的规则集都能写为长度为8的二进制串，这一共有28=256种可能，也就是说规则集一共仅有256个。我们知道，任意一个二进制串都对应一个十进制的数字，比如00110101对应的十进制数是53。所以，采用这种用10进制数字编码的二进制串方法，我们就把规则集进行编码。这种编码的方法很有效，因为任何细胞自动机的规则都逃不出这套编码方案，但是下面我们将看到这种方法有些麻烦，所以我们还常常使用另外一套编码的方法。
如果细胞自动机的邻居半径不是1，那么上述编码方案的长度将会急剧增加。例如一个邻居半径为2的细胞自动机的所有可能输入就是25=32种，因而根据上面的原理，我们的编码也需要32位长，这显然不实际了，因此我们应该能简化该编码方案。考虑这样的规则集，其中每一条规则的输入都仅仅考虑邻居区域的状态数值之和。比如在最简细胞自动机中，某细胞的邻居区域的三个细胞状态是011，则0+1+1=2，这样输入就是2。如果是010呢，那么0+1+0=1，该输入就是1。这样所有的输入可能仅仅有4个包括0,1,2,3。我们把所有的输入列出，按照类似上面的方法就给每个输入指定输出的状态就得到了该编码。比如一条规则的输入输出对应如下：
[[File:屏幕快照 2015-12-12 00.39.50.png|标题1]]
[[File:屏幕快照 2015-12-12 00.41.00.png|标题2]]
把1001也就是9作为该细胞自动集的编码。当邻居半径增大到2的时候，所有可能的输入是5个，所以编码长度是5，显然比刚才简化多了。因而这种编码方案为短编码方案。
=256
=32
1+
1=2
1+0
=
1,2
,
File:屏幕快照 2015-12-12 00.39.50.png|标题1
File:屏幕快照 2015-12-12 00.41.00.png|标题2
=== “方格宇宙”的动态行为 ===
=== “方格宇宙”的动态行为 ===
对于
对于