什么是元胞自动机？| 集智百科
图1：由志愿者March提供的元胞自动机示例生命游戏
“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！
今天分享复杂性科学领域里面一个典型而有趣的模型：元胞自动机。本文将介绍元胞自动机的基本概念，有哪些好玩的游戏，知名的研究者、机构以及一些入门的学习资料。
目录
1. 什么是元胞自动机?
2. 相关概念介绍
3. 知名学者简介
4. 学习资源（课程与书籍）
5. 项目志愿者招募
1.什么是元胞自动机？
1.什么是元胞自动机？
元胞自动机（Cellular Automata，或翻译为细胞自动机、点格自动机）是一种在空间和时间上都离散的演化动力系统。系统由正方形、三角形或者立方体等基本几何元素的元胞（Cell）组成，这些元胞按照一定规则排列可以形成一个空间区域，然后每个元胞之上都有若干种离散或者连续的状态，这些状态在每一个时间步都会按照相同的规则发生变化，于是形成了整个元胞自动机的演化过程。
人们通常通过元胞自动机来研究从局部简单的规则到整体复杂动态的涌现过程。元胞自动机自产生以来，被应用在社会、经济、军事等各个研究领域，也有相关的扩展模型，比如沙堆模型、投票模型等。
2. 相关概念介绍
康威的生命游戏 Conway’s Game of Life
生命游戏是一个零玩家参与的游戏，由英国数学家约翰·康威（John Conway）在1970年发明的元胞自动机，刊登在当年的《科学美国人》上。
在一个无数格子的网格（元胞）中，每个元胞有两种状态：死（白格）或活（黑格），而下一回合的状态完全受它周围8个元胞的状态而定。按照以下三条规则进行演化：
a. 活元胞（黑格）周围的细胞数如果小于2个或多于3个则会死亡；（离群或过度竞争导致死亡）
b. 活元胞（黑格）周围如果有2或3个细胞可以继续存活；（正常生存）
c. 死细胞（白格）周围如果恰好有3个细胞则会诞生新的活细胞。（繁殖）
给定初始状态（通常称为种子），根据简单的规则，就能演化出复杂的生命现象。
效果如下：
布莱恩的大脑 Brain’s Brain
布莱恩·西尔弗曼（Brian Silverman）是加拿大计算机科学家,他设计了很多有趣的元胞自动机规则，其中经典的是Brain’s Brain和The WireWorld。Brain’s Brain是由一个无线的二维细胞网格组成，每个细胞处于3种状态，类比大脑，可以把细胞现象成是神经元，三种状态对应的是：开（刺激）、关（关闭但是准备好刺激）、死（刺激但是没有反应），同时该细胞受周围8个细胞的影响，从而发生演化。
图4：一个典型的混沌的Brain’s Brain模式，展示了各种形状：宇宙飞船、耙、和对角线波。在这个动画中，处于开状态的细胞是白色的。处于死亡状态的细胞是蓝色的。
朗顿的蚂蚁 Langton’s ant
朗顿的蚂蚁是元胞自动机一个经典的示例。它由克里斯托夫·兰顿在1986年提出，它是一个由黑白格子和一只”蚂蚁”构成的二维图灵机。设置具体规则如下：
-
如果蚂蚁位于白色方块，则向右旋转 90°，反转方块的颜色，然后向前移动一步。 -
如果蚂蚁位于黑色方块，则向左旋转 90°，反转方块的颜色，然后向前移动一步。
效果如下：
图6：当朗顿蚂蚁程序进行到10000步时，它会自动生成路线进行繁衍
除了颜色反转，还可以让蚂蚁调整方向或者定义多种颜色进行循环，从而产生更加复杂的图案。
图7：L2NNL1L2L1: 六边形循环生长
冯·诺依曼元胞自动机von Neumann cellular automaton
冯·诺依曼元胞自动机是元胞自动机最原始的表达方式。在冯 · 诺依曼的细胞自动机中，有限状态机（或细胞）被安排在一个二维的笛卡尔网格中，并与周围的4个元胞作用。因为冯 · 诺依曼的细胞自动机是第一个使用这种安排的例子，被称为冯·诺依曼邻居（von Neumann neighbourhood）。与此相对的是，摩尔邻居（Moore neighborhood），是指元胞受到周围的8个相邻元胞的共同作用。
图8：一个简单的冯·诺依曼元胞自动机的配置。
冯·诺依曼 von Neumann
图9：冯·诺依曼 von Neumann
集智俱乐部也编写过文章以供大家更充分的探索冯·诺依曼的思想：
在文内预测了复杂性科学未来100年的发展方向，而且还指出了生命逻辑最核心的奥秘：热力学、信息论与自指之间的深刻联系。
克里斯托弗·朗顿 Christopher Langton
克里斯托弗·朗顿（Christopher Langton ），美国计算机科学家，人工生命领域的创始人之一。在密歇根大学读研究生的时候，创建了朗顿蚂蚁和朗顿循环。同时他在20世纪80年代末创造了人工生命这个术语，当时他于1987年在洛斯阿拉莫斯国家实验室组织了第一次“生命系统的合成和模拟研讨会”。在洛斯阿拉莫斯任职之后，朗顿加入了圣塔菲研究所（SFI)，继续他的人工生命研究 。
约翰·何顿·康威（John Horton Conway）
图11：约翰·何顿·康威（John Horton Conway）
释放比特自由——Wolfram的“一种新科学”介绍：
http://rrd.me/fXUfT
2.《元胞自动机与复杂性论文集》 Cellular Automata and Complexity: Collected Papers
这本书是一个论文合集，主要收集了Wolfram关于元胞自动机和复杂性研究的原始论文，有一些是科学界广为人知的论文，有一些也从来没有发表过。
元胞自动机已经成为了一个新的研究领域，在物理学、经济学和计算机科学许多影响具有非常重要的影响。
元胞自动机与复杂性论文集 Cellular Automata and Complexity: Collected Papers： http://rrd.me/gcq4W
元胞自动机: 理论与实验 Cellular automata: Theory and experiment： http://rrd.me/gcq8X
《自复制自动机理论》中文版译稿整理集： http://url.cn/53ztts
元胞自动机：一个离散的宇宙 Cellular Automata: A Discrete Universe http://rrd.me/gcqBH
课程链接： https://campus.swarma.org/play/coursedetail?id=429
以上的内容都只是非常简单的介绍，我们希望可以针对上面的每个知识点都进行扩充，使其变成一个可被大家广泛学习的科学词条。待建立的词条如下，共计15条。
知识概念
元胞自动机（Cellular Automata）
康威生命游戏 （Conway’s Game of Life）
布莱恩的大脑（Brain’s Brain）
朗顿蚂蚁（Langton’s ant ）
冯·诺依曼元胞自动机（von Neumann cellular automata）
The Wireworld
备注：以上词条需要附上代码演示和结果说明。
人物
布莱恩·西尔弗曼（Brian Silverman）
冯·诺依曼（von Neumann）
约翰·何顿·康威（John Horton Conway）
史蒂芬·沃尔夫勒姆（Stephen Wolfram）
资源
《A New Kind of Science》
《Cellular Automata and Complexity: Collected Papers》
《Cellular automata: Theory and experiment》
《Theory of Self-reproducing Automata》
《Cellular Automata: A Discrete Universe》
本期招募5位对这个主题感兴趣的小伙伴，一起来填充内容，计划在一周之内完成，会提供相关的参考资料和模板，主要的工作是翻译和整理。请感兴趣的小伙伴扫码添加负责人微信，并备注：元胞自动机。
来源：集智百科 编辑：曾祥轩
推荐阅读
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！
本篇文章来源于微信公众号: 集智俱乐部
微信扫一扫,分享到朋友圈
