引言
细胞自动机（Cellular Automaton）是由数学家冯·诺依曼和乌拉姆提出的离散计算模型。在这个模型中，空间被划分为规则的网格，每个网格单元（细胞）根据局部邻居状态和预设规则同步更新。令人惊讶的是，这一极简的模型能够产生从周期性振荡到混沌边缘的复杂行为，甚至具有图灵完备性。
本文将用Java实现两个经典的细胞自动机：一维Rule 110（已被证明图灵完备）和二维康威生命游戏（最著名的人工生命模拟）。通过这两个实现，读者将理解局部规则如何涌现全局复杂性。
一维细胞自动机与Rule 110
规则编码
在一维细胞自动机中，每个细胞仅有两种状态（0或1），下一时刻的状态由自身和左右两个邻居共3个细胞的状态决定。3个二进制位共有 $2^3 = 8$ 种组合，每种组合对应下一状态为0或1，因此总共有 $2^8 = 256$ 种规则，编号为Rule 0到Rule 255。
Rule 110的规则表如下（二进制编码01101110 = 110）：
| 邻居模式 | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| 下一状态 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
2004年，Matthew Cook证明了Rule 110是图灵完备的，这意味着它可以模拟任何图灵机，能够执行任意计算。
Java实现
import javax.swing.*;
import java.awt.*;
import java.awt.image.BufferedImage;
/**
* 细胞自动机模拟器
* 包含一维Rule 110和二维康威生命游戏
*/
public class CellularAutomaton extends JPanel implements Runnable {
// ==================== 一维Rule 110 ====================
/**
* 计算Rule 110的下一行状态
* @param current 当前行状态数组
* @return 下一行状态数组
*/
public static int[] nextGenerationRule110(int[] current) {
int n = current.length;
int[] next = new int[n];
for (int i = 0; i < n; i++) {
// 获取左、中、右三个邻居（循环边界）
int left = current[(i - 1 + n) % n];
int center = current[i];
int right = current[(i + 1) % n];
// 将3位二进制转换为0-7的索引
int pattern = (left << 2) | (center << 1) | right;
// Rule 110: 01101110 (从111到000)
// 对应关系: 111->0, 110->1, 101->1, 100->0, 011->1, 010->1, 001->1, 000->0
switch (pattern) {
case 7: next[i] = 0; break; // 111
case 6: next[i] = 1; break; // 110
case 5: next[i] = 1; break; // 101
case 4: next[i] = 0; break; // 100
case 3: next[i] = 1; break; // 011
case 2: next[i] = 1; break; // 010
case 1: next[i] = 1; break; // 001
case 0: next[i] = 0; break; // 000
}
}
return next;
}
/**
* 通用一维细胞自动机：根据规则号生成下一行
* @param current 当前行
* @param ruleNumber 规则号(0-255)
*/
public static int[] nextGeneration1D(int[] current, int ruleNumber) {
int n = current.length;
int[] next = new int[n];
for (int i = 0; i < n; i++) {
int left = current[(i - 1 + n) % n];
int center = current[i];
int right = current[(i + 1) % n];
int pattern = (left << 2) | (center << 1) | right;
// 从ruleNumber中提取对应位的值
next[i] = (ruleNumber >> pattern) & 1;
}
return next;
}
// ==================== 二维康威生命游戏 ====================
/**
* 计算康威生命游戏的下一代
* 规则：
* 1. 活细胞邻居数为2或3时存活
* 2. 死细胞邻居数恰好为3时复活
* 3. 其他情况死亡
*/
public static int[][] nextGenerationLife(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int[][] next = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int neighbors = countNeighbors(grid, i, j);
if (grid[i][j] == 1) {
// 活细胞：2或3个邻居存活
next[i][j] = (neighbors == 2 || neighbors == 3) ? 1 : 0;
} else {
// 死细胞：恰好3个邻居时复活
next[i][j] = (neighbors == 3) ? 1 : 0;
}
}
}
return next;
}
/**
* 统计(i,j)位置的8邻域活细胞数量（循环边界）
*/
private static int countNeighbors(int[][] grid, int row, int col) {
int count = 0;
int rows = grid.length;
int cols = grid[0].length;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (di == 0 && dj == 0) continue;
int ni = (row + di + rows) % rows;
int nj = (col + dj + cols) % cols;
count += grid[ni][nj];
}
}
return count;
}
/**
* 初始化随机网格
*/
public static int[][] initRandomGrid(int rows, int cols, double density) {
int[][] grid = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
grid[i][j] = Math.random() < density ? 1 : 0;
}
}
return grid;
}
/**
* 初始化滑翔机图案（经典的生命游戏模式）
*/
public static int[][] initGlider(int rows, int cols) {
int[][] grid = new int[rows][cols];
int cx = cols / 2, cy = rows / 2;
// 滑翔机形状
grid[cy][cx + 1] = 1;
grid[cy + 1][cx + 2] = 1;
grid[cy + 2][cx] = 1;
grid[cy + 2][cx + 1] = 1;
grid[cy + 2][cx + 2] = 1;
return grid;
}
/**
* 打印二维网格到控制台
*/
public static void printGrid(int[][] grid) {
for (int[] row : grid) {
for (int cell : row) {
System.out.print(cell == 1 ? "██" : " ");
}
System.out.println();
}
}
// ==================== 可视化与主程序 ====================
private BufferedImage canvas;
private int[][] lifeGrid;
private int mode; // 0=Rule110, 1=Life
private int generation = 0;
public CellularAutomaton(int width, int height, int mode) {
this.mode = mode;
setPreferredSize(new Dimension(width, height));
canvas = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
if (mode == 0) {
// Rule 110：宽度为画布宽度，逐行渲染
lifeGrid = new int[1][width];
lifeGrid[0][width / 2] = 1; // 中间一个种子
} else {
lifeGrid = initRandomGrid(height / 4, width / 4, 0.25);
}
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
g.drawImage(canvas, 0, 0, null);
}
@Override
public void run() {
Graphics2D g = canvas.createGraphics();
if (mode == 0) {
// Rule 110渲染
int[] row = new int[canvas.getWidth()];
row[row.length / 2] = 1;
for (int y = 0; y < canvas.getHeight() && y < row.length; y++) {
for (int x = 0; x < row.length; x++) {
g.setColor(row[x] == 1 ? Color.WHITE : Color.BLACK);
g.drawRect(x, y, 1, 1);
}
row = nextGenerationRule110(row);
repaint();
try { Thread.sleep(10); } catch (InterruptedException e) { break; }
}
} else {
// 生命游戏渲染
int cellSize = 4;
int rows = canvas.getHeight() / cellSize;
int cols = canvas.getWidth() / cellSize;
lifeGrid = initRandomGrid(rows, cols, 0.2);
while (true) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
g.setColor(lifeGrid[i][j] == 1 ? Color.GREEN : Color.BLACK);
g.fillRect(j * cellSize, i * cellSize, cellSize, cellSize);
}
}
lifeGrid = nextGenerationLife(lifeGrid);
generation++;
repaint();
try { Thread.sleep(100); } catch (InterruptedException e) { break; }
}
}
g.dispose();
}
public static void main(String[] args) {
// 控制台演示Rule 110
System.out.println("=== Rule 110 演化（前20代）===");
int[] row = new int[80];
row[40] = 1; // 中间种子
for (int gen = 0; gen < 20; gen++) {
for (int cell : row) {
System.out.print(cell == 1 ? "█" : " ");
}
System.out.println();
row = nextGenerationRule110(row);
}
// 控制台演示生命游戏
System.out.println("\n=== 康威生命游戏（滑翔机，5代）===");
int[][] grid = initGlider(20, 40);
for (int gen = 0; gen < 5; gen++) {
System.out.println("第 " + gen + " 代:");
printGrid(grid);
System.out.println();
grid = nextGenerationLife(grid);
}
// GUI演示（可选）
SwingUtilities.invokeLater(() -> {
JFrame frame = new JFrame("细胞自动机");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
CellularAutomaton ca = new CellularAutomaton(800, 600, 1); // 1=生命游戏
frame.add(ca);
frame.pack();
frame.setLocationRelativeTo(null);
frame.setVisible(true);
new Thread(ca).start();
});
}
}
算法分析
时间复杂度
对于二维生命游戏，设网格大小为 $n \times m$，每代更新的时间复杂度为 $O(n \times m)$，因为每个细胞的下一状态计算仅需检查8个邻居。
对于一维Rule 110，长度为 $n$ 的数组每代更新时间为 $O(n)$。
空间复杂度
需要存储当前代和下一代两个网格，空间复杂度为 $O(n \times m)$。可以通过位运算优化，将8个细胞打包到一个字节中，减少内存占用。
计算不可约性
Stephen Wolfram提出的计算不可约性原理指出：对于许多细胞自动机（包括Rule 110），不存在比直接模拟更快的算法来预测其长期行为。这意味着这些系统的复杂性是内在的，无法被”压缩”。
扩展应用
复杂模式的生命游戏
康威生命游戏中存在许多有趣的稳定结构：
– 静物（Still Life）：方块、蜂巢、船等不会变化的图案
– 振荡器（Oscillator）：闪光灯、蟾蜍、烽火等周期性变化图案
– 太空船（Spaceship）：滑翔机、轻/中/重型太空船等移动图案
这些结构可以作为逻辑门的基础，已有人实现了完整的图灵机在生命游戏中运行。
实际应用领域
- 并行计算模型：细胞自动机天然适合GPU并行计算
- 物理模拟：流体力学中的格子玻尔兹曼方法（LBM）就是细胞自动机的推广
- 图像处理：形态学操作、边缘检测可以用细胞自动机规则实现
- 密码学：某些规则可生成伪随机序列，用于流密码
总结
细胞自动机展现了简单规则涌现复杂行为的核心原理。Rule 110的图灵完备性证明，即使是最简单的局部规则也能支持通用计算；康威生命游戏中的滑翔枪、逻辑门构造则展示了非平凡结构的自组织现象。通过Java实现这两个经典模型，我们不仅学习了离散动力系统的模拟方法，更深刻理解了计算的本质——复杂性往往源于规则的迭代应用，而非规则本身的复杂度。
