用 ncurses terminfo 实现的 Minsky 机器

# ncurses terminfo 中的 Minsky 机器 Source: https://seriot.ch/computation/terminfo/ ### Nicolas Seriot #### Computation (https://seriot.ch/computation/)\> ncurses terminfo 中的 Minsky 机器 *ncurses terminfo 的参数展开可以模拟二计数器 Minsky 机器。* *在你的终端里寄生运行一个 Fibonacci 程序，以 /usr/bin/top 提供时钟节拍。* *2026年10月2日* ### 1. 引言 早在 2019 年，Gwen Weinholt（weinholt.se (https://weinholt.se/articles/terminfo-and-its-dsl/)）就注意到，Terminfo 包含一个带参数的栈机，具备算术与逻辑运算、if-then-else、输出以及持久化变量。Gwen 指出 terminfo 已经很接近图灵机，只是缺少循环结构，而循环可以通过把迭代推到语言之外来绕过。 最近，Martin Tournoij 实现了 Gotermfo 包（https://pkg.go.dev/zgo.at/termfo#section-readme），并指出*"terminfo 文件是图灵完备的"*。 本文在这些观察的基础上，通过从二计数器 Minsky 机器（https://www.sciencedirect.com/science/article/pii/S0304397596000813）出发的归约，将通用性论证明确化。 ### 2. Terminfo 是一门小型编程语言 早期的物理终端使用各种转义序列来移动光标、删除字符、用粗体或彩色书写等。终端应用程序需要知道终端支持哪些转义序列。`$TERM` 环境变量指定了终端类型，terminfo 数据库描述了它的能力。这个数据库实际上是一组编译后的键值对，通常存放在 `/usr/share/terminfo`。 典型的 macOS Terminal 配置声明了 `TERM=xterm-256color`。运行 `infocmp xterm-256color` 会显示诸多能力，其中包括：`cup=\E\%i%p1%d;%p2%dH`。`cup` 是光标寻址所用的键。curses 提供以 0 为起点的行列参数，而 `%i` 会使前两个参数自增，因为终端转义序列使用从 1 开始的坐标。 这门语言简要介绍如下：[ncurses/tinfo/lib_tparm.c (https://github.com/mirror/ncurses/blob/master/ncurses/tinfo/lib_tparm.c)。本文相关部分如下： | 指令 | 含义 | |------|------| | `%{n}` | 压入整数常量 n | | `%gX` | 压入寄存器 X | | `%PX` | 弹出并存入寄存器 X | | `%=` `%\+` `%\-` | 弹出两个值，压入相等 / 和 / 差 | | `%d` | 弹出并打印 | | `%p1` `%p2` | 压入传给 cup 的行列参数，从 0 开始计数 | | `%?c %t a %e b %;` | 若 c 则执行 a，否则执行 b | | `%? c1 %t a1 %e c2 %t a2 %e b %;` | 若 c1 则执行 a1，否则若 c2 则执行 a2，否则执行 b | 这门语言使用 26 个大写寄存器和 26 个小写寄存器（`A-Z` 和 `a-z`）。大写寄存器是设计为在单个进程内的多次展开之间保持持久的。 有趣的是，我们可以使用自己定义的终端约定，规定例如 curses 移动光标时会发生什么。在下面的例子中，我们编译一个名为 `test` 的终端，其 `cup` 规则会先在第 5 行第 30 列打印 `hello`，然后再把光标移动到请求的位置。 test.txt（https://seriot.ch/computation/terminfo/test.txt）： `` test,cup=\E5;30H hello \E[%i%p1%d;%p2%dH, `` 编译并运行： `` tic test.txt; TERM=test; tput cup 0 0 `` 注意，tic 默认会把用户自定义的条目安装到 `~/.terminfo/` 下。若要在当前目录下编译和查找，请使用 `export TERMINFO="$PWD"`。 因此，我们得到一门带算术运算、持久状态和条件控制流的小型编程语言。正如第 1 节所述，它缺少内部循环。只有反复展开能力（capability expansion）才能提供时钟。 ### 3. terminfo 中的 Minsky 计数器机器 令 `A` 和 `B` 为两个寄存器，`Z` 为程序计数器。 任意一条指令 `i: INC A -> j` 可以编译为： `` if Z == i: A = A+1 Z = j `` 用 terminfo 表示为：`%gA%\{1\}%\+%PA%\{j\}%PZ`。 同理，`j: JZDEC A -> k, l` 变为： `` if Z == j: if A == 0: Z = k else: A = A-1 Z = l `` 我们可以对 `Z` 建立一条 `if / else-if` 链，每条分支对应一条指令。每次展开执行机器的一步，反复的展开提供时钟。 这直接实现了二计数器 Minsky 机器的指令集。在理想化的无界计数器和能力大小的假设下，**该构造在计算上是通用的**。 在实际中，具体的 ncurses 实现对寄存器取值和 terminfo 条目大小都有上界，因此任何实际实例都是有限状态的。 ### 4. 加法 这里是一台加法机，易于检查和理解。它计算 4 + 9 = 13。每次展开都会把当前状态打印到 stdout，程序不会发出最终的光标移动转义序列。 Minsky 程序： `` 0: A=4, B=9, Z=1 # 初始化 1: JZDEC B,3,2 # 若 B 为空则停机 2: INC A,1 # 从 B 向 A 移动一个单位 3: HALT # 停机 `` add.txt（https://seriot.ch/computation/terminfo/add.txt）： `` add,cup= # if (Z == 0) { A = 4; B = 9; Z = 1 } %?%gZ%{0}%=%t %{4}%PA %{9}%PB %{1}%PZ # else if (Z == 1) { if (B == 0) { Z = 3 } else { B = B-1; Z = 2 } } %e%gZ%{1}%=%t %?%gB%{0}%=%t %{3}%PZ %e %gB%{1}%-%PB %{2}%PZ %; # else if (Z == 2) { A = A + 1; Z = 1 } %e%gZ%{2}%=%t %gA%{1}%+%PA %{1}%PZ # else if (Z == 3) { HALTED } %e%gZ%{3}%=%t %; # 打印本次展开执行后的追踪 Z=%gZ%d A=%gA%d B=%gB%d\n, `` 通过将规则展开 20 次（机器停机前所需的展开次数）来编译和运行： `` tic add.txt TERM=add; yes 'cup 0 0' | head -n 20 | tput -S `` 输出的最后一行： `` Z=3 A=13 B=0 `` ### 5. Fibonacci 与加法机类似，我们可以用 3 个寄存器构建一台 Fibonacci 机器： `` A = F(N-1) B = F(N) N = 当前 Fibonacci 索引，同时用作初始化标志 `` fib.txt（https://seriot.ch/computation/terminfo/fib.txt）： `` fib,cup= %?%gN%{0}%=%t%{0}%PA%{1}%PB%{1}%PN %e%gA%gB%+%gB%PA%PB%gN%{1}%+%PN%; A=%gA%d B=%gB%d N=%gN%d F(%gN%d)=%gB%d\r\n, `` 这些行的含义是： `` if (N == 0) { A = 0; B = 1; N = 1; } else { 栈：B' = A + B，A' = 原来的 B；N = N + 1； } 打印追踪行 `` 编译并运行： `` tic fib.txt TERM=fib; yes 'cup 0 0' | head -n 10 | tput -S `` 因此，使用 head -n 10 时最后一行是： `` A=34 B=55 N=10 F(10)=55 `` ### 6. 以 /usr/bin/top 提供时钟的 Fibonacci 前面的机器由 `yes` 提供时钟，它会反复输出同一行。 一个有趣的变体是由另一个程序提供时钟——它会以固定间隔重绘屏幕。 例如，`/usr/bin/top` 每秒重绘一次头部时钟。在我的环境上，这会导致当秒数字段被重绘时发出一次 `cup\(0,78\)` 调用。这一光标移动本身就可以用作时钟（用时钟作为时钟……）。具体的坐标取决于 `top` 的布局和终端大小。 fib_top.txt（https://seriot.ch/computation/terminfo/fib_top.txt）： `` fib_top,cup= # 当 top 在 (0,78) 处寻址秒数位时，前进一步 %?%p1%{0}%=%p2%{78}%=%A%t\ %?%gN%{0}%=%t\ %{0}%PA%{1}%PB%{1}%PN\ %e\ %gA%gB%+%gB%PA%PB%gN%{1}%+%PN\ %;\ %; # 在窗口标题中显示当前结果 \E]0;F(%gN%d)=%gB%d\007 # 发出 top 请求的光标移动 \E[%p1%{1}%+%d;%p2%{1}%+%dH, `` 编译并运行： `` tic fib_top.txt TERM=fib_top; /usr/bin/top `` 终端会话 *寄生在你终端中的 Fibonacci 程序，由 /usr/bin/top 提供时钟节拍。结果输出在窗口标题中。* ### 7. 安全影响 这是一个 bug 吗？Fibonacci 示例中没有任何东西需要被"突破"。算术运算、条件判断、持久变量、参数展开以及光标寻址都如预期般工作。意外的行为源于它们的组合，因此这是一种 hack，而不是 bug。 有趣的安全属性在于信任边界：一个由用户控制的 terminfo 程序被反复地由另一个进程内的 ncurses 解释执行。但即使被以 root 权限运行的 setuid 程序（如 `top`）求值，Fibonacci 程序也不是一个提权漏洞利用。Terminfo 参数展开无法打开文件、执行命令或发起系统调用。 这个例子本身只会产生终端输出。只有在该特权上下文中的 terminfo 解析器或参数求值器存在漏洞，才可能造成特权影响。 ### 8. 结论 本文展示了： - terminfo 不只是被动的终端元数据，而是一门带状态的小型编程语言 - 我们可以通过反复展开 ncurses terminfo 来实现一台二计数器 Minsky 机器 - 在理想化的无界计数器和无界展开步数的假设下，该构造在计算上是通用的 - 这些规则可以在宿主进程内部展开，实际上充当一个寄生程序