📖 第4课：规则110与计算通用性

图灵完备 规则110 粒子计算 循环标签系统

🎯 本课目标

理解规则110如何实现计算通用性——这是最简单的一维CA中被证明图灵完备的规则。我们将深入分析规则110中的"粒子"结构，并理解这些粒子如何构成逻辑门和信息传输通道。

🧠 规则110：最简单的通用计算机

规则110（LUT = 01101110）是Wolfram分类中的Class IV CA——介于秩序与混沌之间的"复杂"行为。它的特殊性在于：

🔬 规则110中的粒子结构

规则110产生多种局域结构，称为"粒子"或"局部结构"（Localized Structures）。这些粒子在背景中传播、碰撞、湮灭——它们就是规则110的"计算元件"。

背景与粒子类型

粒子碰撞 = 逻辑运算

当两个粒子碰撞时，可能产生：

• 新粒子（信号传递）
• 粒子湮灭（信号擦除）
• 粒子改变方向（信号路由）

📐 Cook的通用性证明

Matthew Cook在2004年发表的证明是CA理论最重要的结果之一。证明策略：

⚡ 规则110的Verilog实现

// ============================================================================
// ca_rule110.v - 规则110引擎 + 粒子检测器
// 实现规则110演化，并检测特定粒子模式
// ============================================================================
module ca_rule110 #(
    parameter WIDTH = 128,            // 网格宽度（建议≥64以观察粒子）
    parameter DETECT_PARTICLES = 1    // 是否启用粒子检测
)(
    input  wire             clk,
    input  wire             rst_n,
    input  wire             enable,
    input  wire             init,
    input  wire [WIDTH-1:0] seed,
    output wire [WIDTH-1:0] state,
    output wire [3:0]       particle_count,  // 检测到的粒子数
    output wire [31:0]      step_count
);

    // ---- CA状态 ----
    reg [WIDTH-1:0] curr;
    wire [WIDTH-1:0] nxt;

    // ---- 规则110实现 ----
    // f(L,C,R) = ~(L & C & R) & (L | C | R) 的简化
    // 等价于: (L & ~R) | (~L & C) | (C & ~R) | (~C & R & L)
    // 最简形式: (L ^ R) & C | L | R & ~C  -- 但我们直接用真值表
    genvar i;
    generate
        for (i = 0; i < WIDTH; i = i + 1) begin : gen_r110
            wire L = (i == 0)        ? curr[WIDTH-1] : curr[i-1];
            wire C = curr[i];
            wire R = (i == WIDTH-1)  ? curr[0]       : curr[i+1];
            // 规则110: 01101110
            // 直接实现: f = (L & C & ~R) | (~L & C) | (C & ~R) | (~L & ~C & R)
            assign nxt[i] = (~L & C) | (C & ~R) | (L & C & ~R) | (~L & ~C & R);
            // 更简洁: nxt = C ^ (L & C & R) | (~C & (L ^ R))
            // 实际等价于: (~L & C) | (L & ~C) | (C & ~R) | (~C & R)
            // 即: (L ^ C) | (C ^ R) 当去掉000→0和111→0
        end
    endgenerate

    // ---- 步数计数器 ----
    reg [31:0] step_reg;

    // ---- 状态更新 ----
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            curr     <= {WIDTH{1'b0}};
            step_reg <= 32'd0;
        end else if (init) begin
            curr     <= seed;
            step_reg <= 32'd0;
        end else if (enable) begin
            curr     <= nxt;
            step_reg <= step_reg + 32'd1;
        end
    end

    assign state      = curr;
    assign step_count = step_reg;

    // ---- 粒子检测器 ----
    // 检测"粒子"：在背景模式中的局部偏差
    // 简化实现：检测"0110"和"0011"模式（常见的粒子模式）
    generate
        if (DETECT_PARTICLES) begin : gen_detect
            reg [3:0] pcount;
            always @(*) begin
                pcount = 4'd0;
                for (integer j = 0; j < WIDTH-3; j = j + 1) begin
                    // 检测模式 0110（A粒子片段）
                    if (curr[j+3:j] == 4'b0110) pcount = pcount + 1;
                    // 检测模式 0011（B粒子片段）
                    if (curr[j+3:j] == 4'b0011) pcount = pcount + 1;
                end
            end
            assign particle_count = pcount;
        end else begin : gen_no_detect
            assign particle_count = 4'd0;
        end
    endgenerate

endmodule

🔬 循环标签系统模拟器

为了更直观地理解规则110的通用性，我们实现一个独立的循环标签系统，它可以在规则110中被编码。

// ============================================================================
// cyclic_tag_system.v - 循环标签系统
// 证明规则110通用性的中间步骤
// ============================================================================
module cyclic_tag_system #(
    parameter DATA_W   = 64,      // 数据字符串最大长度
    parameter NUM_RULES = 8,       // 产生式规则数量
    parameter RULE_W   = 8        // 每条规则的长度
)(
    input  wire                  clk,
    input  wire                  rst_n,
    input  wire                  run,        // 运行使能
    input  wire [NUM_RULES*RULE_W-1:0] rules, // 产生式规则表
    output wire [DATA_W-1:0]     data_out,   // 当前数据字符串
    output wire [$clog2(NUM_RULES)-1:0] rule_ptr, // 当前规则指针
    output wire                  halted      // 系统停止（数据为空）
);

    // ---- 数据寄存器（移位寄存器） ----
    reg [DATA_W-1:0] data;
    reg [$clog2(NUM_RULES)-1:0] rptr;
    reg [DATA_W-1:0] length;  // 有效数据长度

    // ---- 当前产生式 ----
    wire [RULE_W-1:0] current_rule = rules[rptr * RULE_W +: RULE_W];

    // ---- CTS步骤 ----
    // 1. 检查首bit
    // 2. 若首bit=1，将当前产生式追加到数据末尾
    // 3. 删除首bit（左移）
    // 4. 规则指针循环+1
    wire head_bit = data[0];  // 首bit

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            data   <= {DATA_W{1'b0}};
            rptr   <= 0;
            length <= 0;
        end else if (run && (length > 0)) begin
            // 左移（删除首bit）
            data <= data >> 1;
            length <= length - 1;

            // 如果首bit为1，追加产生式
            if (head_bit) begin
                data[DATA_W-1-:RULE_W] <= current_rule;
                length <= length + RULE_W - 1;  // -1因为删了首bit
            end

            // 规则指针循环
            if (rptr == NUM_RULES - 1)
                rptr <= 0;
            else
                rptr <= rptr + 1;
        end
    end

    assign data_out = data;
    assign rule_ptr = rptr;
    assign halted   = (length == 0);

endmodule

📊 规则110的粒子碰撞表

🏋️ 练习

🏆 成就解锁

📖 扩展阅读

• Cook, M. "Universality in Elementary Cellular Automata", Complex Systems, 15(1):1-40, 2004.
• Wolfram, S. A New Kind of Science, Chapter 11, Wolfram Media, 2002.
• Delorme, M. et al. "Cellular Automata: A Parallel Model", Mathematics and Its Applications, 1999.