整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L10 注解幻灯片。
源网页：10.1 Annotated Slides | Assembly Language, Models of Computation
讲师：Chris Terman。图片直接引用 OCW 原站链接。
L10：汇编语言与计算模型（Assembly Language, Models of Computation）
本讲介绍 Beta 的 UASM 汇编（符号、标号、宏、伪指令），再上升到计算模型：FSM 局限、图灵机、Church 论题、通用机与不可计算性（停机问题），说明 Beta ISA 的图灵完备性。
1. Beta ISA 回顾（Beta ISA Summary）
回顾：32 个通用寄存器 + PC；主存最多 字节（ 个 32 bit 字），指令与数据同存。指令 32 bit：6 bit OPCODE，5 bit Ra/Rb/Rc；两种格式（三寄存器 / 两寄存器+16 bit 常数）。三类：ALU、Load/Store、分支与跳转。
2. 编程语言（Programming Languages）
手写二进制编码不现实 → 汇编用符号写 opcode 与操作数；仍需管寄存器与指令序列。高级语言再升一层：变量与数学运算。本讲 UASM；下讲 C→汇编。还可再叠解释器（如 C 实现 Python）——选合适语言表达，经多层翻译落到 Beta 指令。
3. 汇编语言（Assembly Language）
汇编器读文本 → 产出初始化主存的 32 bit 字数组。BSim 内建 UASM：实质是花哨计算器——求值算术表达式得字节，依次填入字节数组。支持符号/标号命名值与地址，宏封装指令/数据的字段拼装。
4. UASM 源文件例子（Example UASM Source File）
通常一行一条语句。注释：// 至行末，或 /* … */ 跨行。
- 符号（symbol）：常量的名字，如
N=12；改一处即可。R0–R31 预定义为 0–31，便于区分寄存器与立即数 - 标号（label）：某内存地址的名字（如下文
loop）
5. 如何汇编？（How Does It Get Assembled?）
维护符号表（初含寄存器符号）。逐行：定义符号/标号、展开宏、求值写字节。例：N=12 入表；ADDC(r31,N,r1) 展开为地址 0 的 32 bit 字；loop: 记下当前地址后展开 MUL。
两遍扫描：第一遍收齐符号/标号；第二遍生成二进制 → 支持前向引用（如向前分支）。
6. 寄存器是预定义符号（Registers Are Predefined Symbols）
寄存器无魔法：只是 0–31 的符号。ADDC(r31,N,r1) 实际变成 ADDC(31,12,1)。若把寄存器符号用在期望立即数处（或反之），UASM 仍按数值解释——操作数含义由 opcode 宏决定，不由写法直觉决定，写汇编须清醒。
7. 标号与偏移（Labels and Offsets）
分支用相对下一条指令的字偏移（ 指向分支自身）。宏内嵌偏移公式：程序员写目标标号，UASM 算 16 bit 补码。例：BNE 回跳 3 条 → 偏移 。
8. 强大的宏指令（Mighty Macroinstructions）
宏：参数替换后当原文再处理，可嵌套。WORD/LONG 把值拆成 2/4 字节。Beta 为 little-endian：最低有效字节在最低地址（如 0xDEADBEEF 在 0x100 处先存 0xEF）。亦有 big-endian；跨 ISA 传多字节值常需转换。名称源自《格列佛游记》大小端之争。
9. 指令的汇编（Assembly of Instructions）
辅助宏 BETAOP：三寄存器格式；.align 4 保证字对齐；LONG 拼字段：各域 % 截断再 << 到位。BETAOPC 处理含 16 bit 常数的格式。例：ADDC 把 opcode 0x30、RA、常数、Rc 移位或运算拼成一字——“assemble” 字面义。
10. 汇编例子（Example Assembly）
一次 ADDC 的完整宏展开链：格式与 opcode 知识封在宏体里。换一套宏定义，UASM 可服务几乎任意 ISA。
11. Beta 指令的 UASM 宏（UASM Macros for Beta Instructions）
定义在 beta.uasm（实验会 include）。便利宏：分支常丢弃 PC+4 → 两参数形式默认 Rc=R31，少打字、更易读。
12. 伪指令（Pseudoinstructions）
可读性宏：BR() 代替 BEQ(R31,…)；BF/BT 配合比较结果；PUSH/POP 展开为多指令操作 SP 栈。称 pseudoinstructions：表面上更大指令集，底层仍是 L09 那套。
13. 用伪指令写阶乘（Factorial with Pseudoinstructions）
例：CMOVE 表示“装小常数”，比展开后的 ADDC（加到 0）更易懂。减少认知噪音长期受益。
14. 原始数据（Raw Data）
LONG 分配并初始化数据；标号记地址（如 N→0，factN→4）。LD 便利宏默认 Ra=R31：地址 = 0 + 常数（标号值）→ 把该处字装入寄存器。
15. UASM 表达式与布局（UASM Expressions and Layout）
表达式在汇编时求值，不生成运行时 ADD/MUL。特殊符号 .（dot） = 下一个将填充的地址；初值 0，每写一字节递增。可赋 . 指定放置位置；k: 等价 k=.；也可增大 . 预留未初始化数组空间。
16. 小结：汇编语言（Summary: Assembly Language）
汇编 = 方便生成指令/数据二进制并跟踪地址。UASM：值、符号、标号、宏、.。鸡生蛋：第一个汇编器靠手工汇编二进制，再逐步加符号/宏等特性——且务必备份二进制。
17. 通用性？（Universality?）
NAND 对布尔函数通用。ISA 是否通用？能解 FSM 能解的问题吗？有 FSM 不能解的吗？Beta 能否解？答案依赖计算的数学模型。
18. 计算模型（Models of Computation）
CS 根源之一：比较各模型能表示的计算类，寻找通用模型——凡其它良构模型能描述的，通用模型也能。候选：FSM（时序逻辑可建；可用布尔与转移图 100% 预测行为）。FSM 是否万能数字计算装置？
19. FSM 的局限（FSM Limitations）
括号匹配：判定括号串是否良构（每个开括号有对应闭括号）。FSM 用有限状态记历史——括号检查需计数未匹配开括号，但状态数有上限 → 输入开括号过多则无法正确判定。
有限性限制了需无界计数的问题。转向 Alan Turing 的模型。
20. 图灵机（Turing Machines）
1930 年代 Turing 提出：FSM + 无限纸带（可读写）。输入编码在带上；FSM 读写、改态、写答案后停机 → 图灵机（TM）。
有限非空白输入可编码成大整数；TM 实现整数到整数的函数。FSM 真值表可枚举并赋索引 → 谈“TM 347 在输入 51 上得 42”。
21. 其它计算模型（Other Models of Computation）
Kleene、Post、Turing 等（Church 学生）探索递归函数、字符串重写、λ 演算等，并关注不可实现机解决的问题——亦即刻画可解决类。
22. 可计算性？（Computability?）
各模型能算的整数函数集相同（可互译）。Church 论题：凡可实现机可算的离散函数，皆可由某 TM 计算。尚无严格证明，但被普遍接受。“可计算”≈“某 TM 可计算”。不可计算函数见本讲可选视频。
23. 众多图灵机！（Turing Machines Galore!）
每种想做的计算对应一台（不同）TM。这对通用计算机设计有何启示？是否有些计算永远需要专用机？
24. 通用函数（The Universal Function）
希望有 运行 于输入 的结果。 可计算：存在通用图灵机 （且有无穷多；已知最小者约 4 态、6 带符号）。一台通用机可完成任意 TM 能做的计算。
25. 通用性（Universality）
编码“程序”（某 TM 描述）， 编码数据； 解释程序、模拟 。解释编码计算 = 存储程序计算机的核心思想。
26. 图灵通用性（Turing Universality）
通用 TM 是现代通用计算机的范式。证明 ISA 图灵通用：展示能模拟某已知通用 TM。实际机器内存有限 → 仅对放得下的输入等价。门槛不高：有条件分支 + 简单算术 通常即足够。
27. 编码算法：CS 关键（Coded Algorithms: Key to CS）
程序可作为另一程序的数据 → 编译（高级语言→汇编）、软件组件复用、设计面向任务的语言。结论：拟建引擎能做任意可实现机上的计算；通用 TM 为存储程序机铺路 → Beta ISA 够用。
28. 不可计算！（Uncomputability!）
存在良定义离散函数，无任何 TM 能在有限步对任意有限输入算出 ——可证明算法不存在。最著名：停机函数——给定 ，判定第 个 TM 在输入 上是停机还是永远循环。
29. 为何 不可计算（Why fH is Uncomputable）
反证：若停机函数可算，则有 。构造“nasty”机 ： 在 停机时循环，在 循环时停机（靠 查询）。再喂 给 ： 必须既停又不停 → 矛盾。故 不存在，停机函数不可计算。