3,094
个编辑
更改
跳到导航
跳到搜索
建立内容为“=一维基础元胞自动机= == 一维元胞自动机的模拟程序== <htmltag tagname="iframe" src="/applets/onedimCA/cellular_automata_viz.html" style="displa…”的新页面
=一维基础元胞自动机=
== 一维元胞自动机的模拟程序==
<htmltag tagname="iframe" src="/applets/onedimCA/cellular_automata_viz.html" style="display: block; margin-bottom: 1em; width: 900px; height: 640px; border: solid 1px #ddd;"></htmltag>
==基础元胞自动机==
最简单的元胞自动机就是一维的元胞自动机。每个元胞都有黑、白两种颜色。邻居是一个半径为1的区域，每个元胞都有左右两个邻居。这样每一个方格单元和它的邻居可以表示如下：
<center>
<table border="1" cellpadding="0" cellspacing="0" bordercolor="#999999">
<tr bgcolor="#FFFFFF">
<td width="25" height="25"> </td>
<td width="25" height="25" bgcolor="#666666"> </td>
<td width="25" height="25" bgcolor="#000000"> </td>
<td width="25" height="25" bgcolor="#666666"> </td>
<td width="25" height="25"> </td>
</tr>
</table>
</center>
由于每个元胞有两个状态{0,1}，这样，当前元胞加上左右两个邻居一共就有8种状态：
<center>
[[File:8种状态.png|屏幕快照 2015-12-11 23.34.46.png]]
</center>
他们表示的状态分别是：000，001，010，011，100，101，110，111，其中0表示白色，1表示黑色。
===规则与编号===
下面考虑规则，假设当前考虑的细胞为<math>c_i</math>，他在t时刻的状态为<math>s_{i,t}</math>，而它的两个邻居状态为<math>s_{i-1,t}</math>,<math>s_{i+11,t}</math>,则<math>c_i</math>，,在下一时刻的状态为<math>s_{i,t+1}</math>,则转换规则用函数表示为：
<center><math>s_{i,t+1}=f(s_{i-1,t},s_{i,t},s_{i+1,t})</math></center>
其中，<math>s_{i,t}</math>∈{0,1}，对于任意的i和t。
由于元胞自动机的规则就是根据每个元胞和它的邻居的当前状态转移到下一个时刻该元胞的状态。无论规则是什么样的黑箱，它的输入就是上面列出的8种组合之一，因为表示的是每个元胞下一时刻的状态，而状态只可能有0、1两种，则规则的输出要么是0，要么是1。这样，任何一个规则都是一个或者一组转换，比如下图表示的就是一条规则：
<center>
[[File:规则1.png|屏幕快照 2015-12-11 23.36.07.png]]
</center>
另外，若有一个规则是：“如果输入的三个元胞中黑色方格只有1个，那么下一时刻当前元胞就是黑色”可以表示成下面的图：
<center>
[[File:规则2.png|屏幕快照 2015-12-11 23.36.54.png]]
</center>
下面我们再把目光转到规则集上。由于每一条规则都是一个状态或一组状态的转换，那么把输入的8种可能情况转换到当前元胞的下一状态。我们可以用一个转换表表示一组规则集，例如：
<center>
[[File:规则3.png|屏幕快照 2015-12-11 23.37.37.png]]
</center>
这个规则集也可以用下面的一组数字表示为：
<center>
[[File:规则集1.png|屏幕快照 2015-12-12 00.36.36.png]]
</center>
那么这组规则就对应着编码：10100011，也就是把八个位置上的方格进行一个排列。我们可以把输出部分的二进制编码转换成十进制数的形式：163，这就是该细胞自动机的编码。当状态数增多，半径增大的时候，这种编码方式就不实用了，我们需要用另一种方式来编码。考虑下面这样的规则若有一个规则是：“如果输入的三个方格中黑色方格只有1个，那么下一时刻当前方格就是黑色；如果有两个黑色方格，则下时刻是白色，如果有三个方格，则下时刻是黑色，如果有4个方格，那么下一时刻是白色”可以表示成下面的函数表：
<center>
<math>s_{i,t+1}=1</math>, 如果<math>s_{i-1,t}+s_{i,t}+s_{i+1,t}=1</math>
</center>
<center>
<math>s_{i,t+1}=0</math>, 如果<math>s_{i-1,t}+s_{i,t}+s_{i+1,t}=2</math>
</center>
<center>
<math>s_{i,t+1}=1</math>, 如果<math>s_{i-1,t}+s_{i,t}+s_{i+1,t}=3</math>
</center>
<center>
<math>s_{i,t+1}=0</math>, 如果<math>s_{i-1,t}+s_{i,t}+s_{i+1,t}=0</math>
</center>
<center>
其中<math>s_{i,t}\in\{0,1\}</math>, 对于任意的i和t
</center>
这种情况下，输入就仅仅有4种情况，因此可以得到下面的表：
<center>
{|class="wikitable" width="50%"
|输入||0||1||2||3
|-
|输出||0||1||0||1
|}
</center>
同样的道理，我们可以对它进行编码为：0101，表示为十进制就是5。显然，这种编码方式比前一种短，但是这种编码方法不能反映所有的细胞自动机。
每一组规则集也可以表示成类似于上面的图和表，例如下面的另外一组规则
<center>
[[File:规则集2.png|屏幕快照 2015-12-12 00.36.43.png]]
</center>
由于邻居加上当前元胞一共8种状态，每一个状态对应两种可能转换规则，所以规则一共就有<math>2^8=256</math>种，我们可以为每一个规则编码，然后对其进行穷举。
===动态行为===
下面我们来考察这256中元胞自动机所具备的可能动态行为。对于一维的情况，我们假设所有的元胞都分布在一条直线上，并且直线的长度为300，也就是说有300个元胞在这条直线上，那么一条断续的横线就是当前所有细胞状态的一种分布。这些方格随着时间变化，就形成了不同的横线。我们把这些随着时间变化的线纵向拼在一起形成了一个网格区域。其中纵轴表示时间的流逝（往下为正），横轴为“元胞自动机在对应时刻的状态，就能得到一幅图像：
<center>
[[File:元胞自动机图像.png|屏幕快照 2015-12-12 00.42.38.png]]
</center>
这个元胞的每一行都是某一个时刻元胞自动机的状态。因而从上到下数第1、2、3、4、5、6行可以分别表示第1、2、3、4、5、6时间步的元胞自动机状态。因此这里的一个平面的图案就是元胞自动机在时间上的发展动态。下面我们分别挑选几种典型的动态情况示于下图（下方的数字是元胞自动机的编码）：
<center>
[[File:动态情况1.png|屏幕快照 2015-12-12 00.42.44.png]]
[[File:动态情况2.png|屏幕快照 2015-12-12 00.44.21.png]]
</center>
<center>
<gallery mode="packed">
File:184号.jpg|CA 00：184号
File:250号.jpg|CA 01：250号
File:254号.jpg|CA 02：254号
File:300号.jpg|CA 03：300号
</gallery>
</center>
经过对比分析，我们把细胞自动机归为四种类别，它们分别是：
*固定值型：细胞自动机经过若干步运算便停留在一个固定的状态；
*周期型：细胞自动机在几种状态之间周期循环；
*混沌型：细胞自动机处于一种完全无序随机的状态，几乎找不到任何规律；
*复杂型：细胞自动机在运行的过程中可能产生复杂的结构，这种结构既不是完全的随机混乱，又没有固定的周期和状态。
== 一维元胞自动机的模拟程序==
<htmltag tagname="iframe" src="/applets/onedimCA/cellular_automata_viz.html" style="display: block; margin-bottom: 1em; width: 900px; height: 640px; border: solid 1px #ddd;"></htmltag>
==基础元胞自动机==
最简单的元胞自动机就是一维的元胞自动机。每个元胞都有黑、白两种颜色。邻居是一个半径为1的区域，每个元胞都有左右两个邻居。这样每一个方格单元和它的邻居可以表示如下：
<center>
<table border="1" cellpadding="0" cellspacing="0" bordercolor="#999999">
<tr bgcolor="#FFFFFF">
<td width="25" height="25"> </td>
<td width="25" height="25" bgcolor="#666666"> </td>
<td width="25" height="25" bgcolor="#000000"> </td>
<td width="25" height="25" bgcolor="#666666"> </td>
<td width="25" height="25"> </td>
</tr>
</table>
</center>
由于每个元胞有两个状态{0,1}，这样，当前元胞加上左右两个邻居一共就有8种状态：
<center>
[[File:8种状态.png|屏幕快照 2015-12-11 23.34.46.png]]
</center>
他们表示的状态分别是：000，001，010，011，100，101，110，111，其中0表示白色，1表示黑色。
===规则与编号===
下面考虑规则，假设当前考虑的细胞为<math>c_i</math>，他在t时刻的状态为<math>s_{i,t}</math>，而它的两个邻居状态为<math>s_{i-1,t}</math>,<math>s_{i+11,t}</math>,则<math>c_i</math>，,在下一时刻的状态为<math>s_{i,t+1}</math>,则转换规则用函数表示为：
<center><math>s_{i,t+1}=f(s_{i-1,t},s_{i,t},s_{i+1,t})</math></center>
其中，<math>s_{i,t}</math>∈{0,1}，对于任意的i和t。
由于元胞自动机的规则就是根据每个元胞和它的邻居的当前状态转移到下一个时刻该元胞的状态。无论规则是什么样的黑箱，它的输入就是上面列出的8种组合之一，因为表示的是每个元胞下一时刻的状态，而状态只可能有0、1两种，则规则的输出要么是0，要么是1。这样，任何一个规则都是一个或者一组转换，比如下图表示的就是一条规则：
<center>
[[File:规则1.png|屏幕快照 2015-12-11 23.36.07.png]]
</center>
另外，若有一个规则是：“如果输入的三个元胞中黑色方格只有1个，那么下一时刻当前元胞就是黑色”可以表示成下面的图：
<center>
[[File:规则2.png|屏幕快照 2015-12-11 23.36.54.png]]
</center>
下面我们再把目光转到规则集上。由于每一条规则都是一个状态或一组状态的转换，那么把输入的8种可能情况转换到当前元胞的下一状态。我们可以用一个转换表表示一组规则集，例如：
<center>
[[File:规则3.png|屏幕快照 2015-12-11 23.37.37.png]]
</center>
这个规则集也可以用下面的一组数字表示为：
<center>
[[File:规则集1.png|屏幕快照 2015-12-12 00.36.36.png]]
</center>
那么这组规则就对应着编码：10100011，也就是把八个位置上的方格进行一个排列。我们可以把输出部分的二进制编码转换成十进制数的形式：163，这就是该细胞自动机的编码。当状态数增多，半径增大的时候，这种编码方式就不实用了，我们需要用另一种方式来编码。考虑下面这样的规则若有一个规则是：“如果输入的三个方格中黑色方格只有1个，那么下一时刻当前方格就是黑色；如果有两个黑色方格，则下时刻是白色，如果有三个方格，则下时刻是黑色，如果有4个方格，那么下一时刻是白色”可以表示成下面的函数表：
<center>
<math>s_{i,t+1}=1</math>, 如果<math>s_{i-1,t}+s_{i,t}+s_{i+1,t}=1</math>
</center>
<center>
<math>s_{i,t+1}=0</math>, 如果<math>s_{i-1,t}+s_{i,t}+s_{i+1,t}=2</math>
</center>
<center>
<math>s_{i,t+1}=1</math>, 如果<math>s_{i-1,t}+s_{i,t}+s_{i+1,t}=3</math>
</center>
<center>
<math>s_{i,t+1}=0</math>, 如果<math>s_{i-1,t}+s_{i,t}+s_{i+1,t}=0</math>
</center>
<center>
其中<math>s_{i,t}\in\{0,1\}</math>, 对于任意的i和t
</center>
这种情况下，输入就仅仅有4种情况，因此可以得到下面的表：
<center>
{|class="wikitable" width="50%"
|输入||0||1||2||3
|-
|输出||0||1||0||1
|}
</center>
同样的道理，我们可以对它进行编码为：0101，表示为十进制就是5。显然，这种编码方式比前一种短，但是这种编码方法不能反映所有的细胞自动机。
每一组规则集也可以表示成类似于上面的图和表，例如下面的另外一组规则
<center>
[[File:规则集2.png|屏幕快照 2015-12-12 00.36.43.png]]
</center>
由于邻居加上当前元胞一共8种状态，每一个状态对应两种可能转换规则，所以规则一共就有<math>2^8=256</math>种，我们可以为每一个规则编码，然后对其进行穷举。
===动态行为===
下面我们来考察这256中元胞自动机所具备的可能动态行为。对于一维的情况，我们假设所有的元胞都分布在一条直线上，并且直线的长度为300，也就是说有300个元胞在这条直线上，那么一条断续的横线就是当前所有细胞状态的一种分布。这些方格随着时间变化，就形成了不同的横线。我们把这些随着时间变化的线纵向拼在一起形成了一个网格区域。其中纵轴表示时间的流逝（往下为正），横轴为“元胞自动机在对应时刻的状态，就能得到一幅图像：
<center>
[[File:元胞自动机图像.png|屏幕快照 2015-12-12 00.42.38.png]]
</center>
这个元胞的每一行都是某一个时刻元胞自动机的状态。因而从上到下数第1、2、3、4、5、6行可以分别表示第1、2、3、4、5、6时间步的元胞自动机状态。因此这里的一个平面的图案就是元胞自动机在时间上的发展动态。下面我们分别挑选几种典型的动态情况示于下图（下方的数字是元胞自动机的编码）：
<center>
[[File:动态情况1.png|屏幕快照 2015-12-12 00.42.44.png]]
[[File:动态情况2.png|屏幕快照 2015-12-12 00.44.21.png]]
</center>
<center>
<gallery mode="packed">
File:184号.jpg|CA 00：184号
File:250号.jpg|CA 01：250号
File:254号.jpg|CA 02：254号
File:300号.jpg|CA 03：300号
</gallery>
</center>
经过对比分析，我们把细胞自动机归为四种类别，它们分别是：
*固定值型：细胞自动机经过若干步运算便停留在一个固定的状态；
*周期型：细胞自动机在几种状态之间周期循环；
*混沌型：细胞自动机处于一种完全无序随机的状态，几乎找不到任何规律；
*复杂型：细胞自动机在运行的过程中可能产生复杂的结构，这种结构既不是完全的随机混乱，又没有固定的周期和状态。