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