2026 春《计算机系统》

第 1 次讨论课:原型机+数据的机器级行为

图灵完备性:12条指令的奇迹

vspm 原型机的指令集仅有 12 条,但它已经具备了计算任何可计算问题的能力。我们通过一个“用加法实现乘法”的真实汇编案例来证明这一点。

1. 数据传输 (状态改变)

图灵机的纸带读写头。能够将数据在内存和寄存器之间移动。

LOAD R1, [ADDR]STORE R1, [ADDR]

2. 算术逻辑 (状态转移)

图灵机的内部状态机。能够对数据进行最基本的运算。

ADD R1, R2SUB R1, R2AND R1, R2

3. 控制流 (纸带移动)

图灵机的左右移动指令。能够根据条件改变执行顺序,实现循环和分支。

JMP [ADDR]JZ R1, [ADDR]
vspm_multiply.asm
; 目标:计算 5 * 3 (即 5 + 5 + 5)
LOAD R1, 5
; R1 = 被乘数 (5)
LOAD R2, 3
; R2 = 乘数/计数器 (3)
LOAD R3, 0
; R3 = 累加结果 (0)

LOOP_START:
JZ R2, LOOP_END
; 如果计数器 R2 为 0,跳出循环
ADD R3, R1
; 结果 R3 = R3 + 5
SUB R2, 1
; 计数器 R2 = R2 - 1
JMP LOOP_START
; 无条件跳转回循环开始

LOOP_END:
STORE R3, [RESULT]
; 将最终结果 15 存入内存