📖 第12课：Langton回路

Langton 自复制虚拟状态信号传播

🔄 Langton回路——自复制的先驱

1984年，Chris Langton设计了一个能自复制的元胞自动机——Langton回路。它比von Neumann的29状态自复制自动机简单得多，只需要8个状态，却能在二维网格中复制自身。

Langton回路的结构：

回路（Loop）：一个由特定状态元胞组成的闭合环，作为"身体"
信号（Signal）：在回路内部传播的信息粒子，控制复制过程
臂（Arm）：从回路延伸出的构建通道，用于建造副本

状态数：8个状态（0=空, 1=回路壁, 2-3=信号, 4-5=臂, 6-7=辅助）

邻域：Moore 8邻居

复制过程

回路内部的信号沿回路传播
当信号到达特定位置时，触发"臂"的生长
臂向外延伸，构建一个新的回路
信号被复制到新回路中
臂缩回，两个回路独立运行
每个回路可以再次复制，形成指数增长

⚡ Langton回路的Verilog模型

8状态Langton回路引擎

// ============================================================================
// langton_loop.v - Langton自复制回路引擎
// 8状态，Moore邻域，简化版实现
// ============================================================================
module langton_loop #(
    parameter WIDTH  = 80,
    parameter HEIGHT = 80
)(
    input  wire                     clk,
    input  wire                     rst_n,
    input  wire                     enable,
    input  wire                     init,
    input  wire [WIDTH*HEIGHT*3-1:0] seed,  // 8状态需要3位/元胞
    output wire [WIDTH*HEIGHT*3-1:0] state,
    output wire [31:0]              generation,
    output wire [31:0]              loop_count   // 检测到的回路数
);

    // ---- 3位/元胞状态存储 ----
    reg [2:0] grid [0:WIDTH*HEIGHT-1];
    reg [2:0] grid_nxt [0:WIDTH*HEIGHT-1];
    reg [31:0] gen_reg;

    // ---- 邻域提取 ----
    // 对每个元胞(x,y)，提取8个Moore邻居的3位状态
    integer idx, x, y, dx, dy, nx, ny;
    reg [2:0] neighbors [0:7];

    // ---- Langton回路的规则表 ----
    // 简化版本：只实现核心的回路传播和复制逻辑
    // 完整规则表需要2^(3*9) = 2^27个条目，这里用函数实现
    function [2:0] langton_rule;
        input [2:0] self;
        input [2:0] nb0, nb1, nb2, nb3, nb4, nb5, nb6, nb7;
        begin
            // 状态定义:
            // 0 = 空(Empty)
            // 1 = 回路壁(Wall)
            // 2 = 信号A(Signal A, 前进信号)
            // 3 = 信号B(Signal B, 复制信号)
            // 4 = 臂尖(Arm tip)
            // 5 = 臂体(Arm body)
            // 6 = 连接点(Junction)
            // 7 = 保留

            langton_rule = 3'd0;  // 默认：空→空

            case (self)
                3'd0: begin  // 空
                    // 如果相邻有臂尖或信号，可能变为新的臂尖或信号
                    if (nb4 == 3'd4 || nb2 == 3'd4)
                        langton_rule = 3'd5;  // 臂体扩展
                    else if (nb6 == 3'd3)
                        langton_rule = 3'd2;  // 新信号
                end
                3'd1: begin  // 回路壁
                    langton_rule = 3'd1;  // 保持壁（除非有特殊条件）
                    if (nb2 == 3'd3 && nb6 == 3'd0)
                        langton_rule = 3'd6;  // 变为连接点（触发臂生长）
                end
                3'd2: begin  // 信号A
                    // 信号沿回路壁传播
                    langton_rule = 3'd1;  // 信号过后恢复壁
                end
                3'd3: begin  // 信号B（复制信号）
                    langton_rule = 3'd1;  // 信号过后恢复壁
                end
                3'd4: begin  // 臂尖
                    langton_rule = 3'd5;  // 臂尖→臂体
                end
                3'd5: begin  // 臂体
                    langton_rule = 3'd1;  // 臂体→壁（固化）
                end
                3'd6: begin  // 连接点
                    langton_rule = 3'd4;  // 产生新臂尖
                end
                default: langton_rule = 3'd0;
            endcase
        end
    endfunction

    // ---- 状态更新 ----
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            gen_reg <= 32'd0;
            for (idx = 0; idx < WIDTH*HEIGHT; idx = idx + 1)
                grid[idx] <= 3'd0;
        end else if (init) begin
            gen_reg <= 32'd0;
            for (idx = 0; idx < WIDTH*HEIGHT; idx = idx + 1)
                grid[idx] <= seed[idx*3 +: 3];
        end else if (enable) begin
            // 计算所有下一状态
            for (y = 0; y < HEIGHT; y = y + 1) begin
                for (x = 0; x < WIDTH; x = x + 1) begin
                    // 提取8个邻居
                    for (dx = -1; dx <= 1; dx = dx + 1) begin
                        for (dy = -1; dy <= 1; dy = dy + 1) begin
                            nx = (x + dx + WIDTH) % WIDTH;
                            ny = (y + dy + HEIGHT) % HEIGHT;
                        end
                    end
                    // 简化：只使用自身和4个正交邻居
                    idx = y * WIDTH + x;
                    grid_nxt[idx] = langton_rule(
                        grid[idx],
                        grid[((y==0)?HEIGHT-1:y-1)*WIDTH+x],  // 上
                        grid[y*WIDTH+((x==WIDTH-1)?0:x+1)],   // 右
                        grid[((y==HEIGHT-1)?0:y+1)*WIDTH+x],  // 下
                        grid[y*WIDTH+((x==0)?WIDTH-1:x-1)],   // 左
                        3'd0, 3'd0, 3'd0, 3'd0  // 对角邻居简化
                    );
                end
            end
            // 更新
            for (idx = 0; idx < WIDTH*HEIGHT; idx = idx + 1)
                grid[idx] <= grid_nxt[idx];
            gen_reg <= gen_reg + 32'd1;
        end
    end

    // 输出打包
    genvar gi;
    generate
        for (gi = 0; gi < WIDTH*HEIGHT; gi = gi + 1) begin : gen_out
            assign state[gi*3 +: 3] = grid[gi];
        end
    endgenerate

    assign generation = gen_reg;
    assign loop_count = 32'd0;  // 简化：未实现回路计数

endmodule

📐 Langton回路与von Neumann自复制机

特性	von Neumann (1966)	Langton (1984)
状态数	29	8
邻域	Moore (8)	Moore (8)
回路大小	~200,000元胞	~150元胞
复制时间	~10^9步	~150步
通用构造器	是	否
可计算性	图灵完备	非图灵完备
可演化性	支持	有限

⚠️ Langton回路的局限：Langton回路只能复制自身，不能构造任意结构（非通用构造器）。它是一个"自复制器"而非"通用构造器"。要实现真正的可演化自复制系统，需要通用构造器+可变程序——这就是第14课"人工生命演化"要探讨的内容。

🏋️ 练习

练习12.1：构造Langton回路的最小初始配置（6×6区域内的回路+信号）。运行仿真，观察复制过程。

练习12.2：修改回路规则，使得复制后的子回路方向不同（旋转90°）。这需要什么改变？

练习12.3：分析Langton回路的"最小信息量"——需要多少位的信号才能触发完整的复制过程？

练习12.4：设计一个12状态的"增强版Langton回路"，支持两个回路合并为一个更大的结构。

练习12.5（挑战）：在Langton回路中实现"变异"——复制过程中偶尔改变一个状态位。观察变异的回路是否仍能复制。

🏆 成就解锁

🏅 自复制观察者

你已经理解了Langton回路——最简单的自复制CA之一。虽然它不如von Neumann的原始设计通用，但其简洁性使得硬件实现成为可能。

✅ 理解Langton回路的8状态模型
✅ 实现简化版回路引擎
✅ 了解自复制与通用构造的区别
✅ 掌握信号传播和臂生长机制

📐 深入分析：Langton回路与von Neumann构造器的对比

详细对比：

Langton回路的设计哲学：最小化状态数和规则复杂度，牺牲通用性

von Neumann构造器的设计哲学：最大化通用性，接受高复杂度

关键差异：

1. 可构造性：Langton回路只能复制自身；von Neumann可以构造任意结构

2. 鲁棒性：Langton回路对噪声敏感（一个状态错误可能导致复制失败）

von Neumann构造器有冗余，对噪声更鲁棒

3. 可演化性：Langton回路的"基因组"太短，几乎没有变异空间

von Neumann的描述带可以编码任意长程序，支持开放演化

硬件实现的可行性：

Langton回路：8状态×Moore邻域，64×64网格，~500 LUTs → 完全可行

von Neumann构造器：29状态×Moore邻域，~450×450网格 → 需要外部存储器

补充实现

// 回路检测器 - 自动检测网格中的完整回路
module loop_detector #(
    parameter WIDTH = 80,
    parameter HEIGHT = 80
)(
    input  wire             clk,
    input  wire             rst_n,
    input  wire [2:0]       grid [0:WIDTH*HEIGHT-1],
    output wire [7:0]       loop_count,
    output wire [15:0]      loop_center_x,
    output wire [15:0]      loop_center_y,
    output wire             detection_valid
);
    // 简化检测：寻找状态1(壁)的闭合环
    // 使用洪泛填充算法从边界开始标记外部区域
    // 未被标记的状态1元胞构成回路
    reg [WIDTH*HEIGHT-1:0] visited;
    reg [7:0] loops;
    reg [15:0] cx, cy;
    integer idx;
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            loops <= 8'd0;
            visited <= {WIDTH*HEIGHT{1'b0}};
        end else begin
            // 简化：统计状态1的连通区域数
            loops <= 8'd0;
            for (idx = 0; idx < WIDTH*HEIGHT; idx = idx + 1) begin
                if (grid[idx] == 3'd1 && !visited[idx]) begin
                    loops <= loops + 8'd1;
                    // 标记连通区域（简化：仅标记当前元胞）
                    visited[idx] <= 1'b1;
                end
            end
        end
    end
    assign loop_count = loops;
    assign loop_center_x = cx;
    assign loop_center_y = cy;
    assign detection_valid = 1'b1;
endmodule

性能与优化分析

自复制CA的研究前沿：

1. 温和自复制（Temperate Self-replication）：复制过程中不消耗母体

2. 可编程自复制：子代的"基因组"可以不同于母代

3. 量子CA中的自复制：量子叠加态下的复制行为

4. 自修复系统：利用自复制机制修复受损的CA结构

📖 扩展阅读

Wolfram, S. A New Kind of Science, Wolfram Media, 2002.
Toffoli, T. & Margolus, N. Cellular Automata Machines, MIT Press, 1987.
Ilachinski, A. Cellular Automata: A Discrete Universe, World Scientific, 2001.

🔬 补充专题：实验方法论

在进行CA实验时，科学的方法论至关重要。以下是一些通用的实验指导原则：

实验设计三要素：

控制变量：每次只改变一个参数，保持其他不变
可重复性：记录所有参数，确保实验可以精确复现
统计显著性：多次运行取平均，避免偶然结果误导

参数扫描方法

系统性地扫描参数空间是理解CA行为的关键技术：

参数	范围	步长	测量指标
规则号	0-255	1	种群密度/周期
初始密度	0.1-0.9	0.1	收敛时间
网格大小	16-256	×2	有限尺寸效应
边界条件	环形/固定/镜像	离散	边界效应

💡 实验记录模板：每次实验记录以下信息——日期、规则号、初始条件、网格大小、边界条件、运行步数、关键观察、数据文件路径。这是科学研究的良好习惯，也使得结果可以追溯和验证。

数据可视化技巧

CA实验产生的数据通常是高维的（空间+时间+状态）。有效的可视化对于理解至关重要：

时空图：横轴=空间位置，纵轴=时间，颜色=状态——最常用的CA可视化方式
相图：x轴=参数A，y轴=参数B，颜色=测量指标——用于参数空间扫描
频谱图：对种群时间序列做FFT，识别周期性
直方图：统计状态/密度的分布

自相关分析：

时间自相关：R(τ) = ⟨n(t)·n(t+τ)⟩ / ⟨n²⟩

空间自相关：C(r) = ⟨n(x)·n(x+r)⟩ / ⟨n²⟩

如果R(τ)以周期T振荡 → 系统有周期T的行为

如果C(r)幂律衰减 → 系统处于临界状态

◀ 第11课 📜 目录第13课 ▶

元胞自动机课程 · 从Conway到Langton到Lattice Gas