二进制图灵机演示

🧩 七元组定义

标准图灵机模型由以下七元组定义：

$$M = \langle Q, \Sigma, \Gamma, \delta, q_0, B, F \rangle$$

$$Q$$: 有限状态集合如 $$Q = \{q_0, q_1, q_2, \text{halt}\}$$

$$\Sigma$$: 输入字母表本实验 $$\Sigma = \{1, +, \times\}$$

$$\Gamma$$: 磁带字母表 $$\Gamma = \{1, +, \times, B, X, Y, \dots\}$$

$$\delta$$: 转移函数 $$\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$$

$$q_0$$: 初始状态通常为 $$q_0 \in Q$$

$$B$$: 空白符号表示磁带上的空单元格

$$F$$: 终止状态集合 $$F \subseteq Q$$，通常包含 $$\text{halt}$$ 状态

$$\delta(q, a) = (q', b, D)$$

→

当前状态 $$q \in Q$$ 机器当前所处的状态

●

读取符号 $$a \in \Gamma$$ 磁头当前位置的字符

✎

写入符号 $$b \in \Gamma$$ 覆盖当前单元格的字符

←/→

移动方向 $$D \in \{L, R\}$$ $$L$$ 向左移动，$$R$$ 向右移动

✓

下一状态 $$q' \in Q$$ 转移后的新状态

"机器根据当前状态和磁带符号决定下一步动作"

基于标准七元组，适配二进制算术运算：

$$M = \langle \{q_0, \dots\}, \{0, 1\}, \{0, 1, +, B, x, y\}, \delta, q_0, B, F \rangle$$

$$\Sigma = \{0, 1\}$$

输入仅接受二进制数字 (0和1)

辅助符号 $$\{x, y\}$$

用于标记已处理的位 (x代表0, y代表1)

💡 运算原理 (Ripple Carry)：机器交替读取两个数字的最低位（右端）。读取右数的一位后，将其擦除，并携带该值向左移动，加到左数对应的位置上，处理进位，然后返回。

Current State

IDLE

Step

Read

BIN

ACTION LOG > 等待指令...

当前算术规则集

$$ q_0 \xrightarrow{0/1} R, \quad q_{add} \xrightarrow{Carry} L, \quad q_{return} \xrightarrow{Find \ Y} R $$