🧩 七元组定义

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

$$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
0
Read
-
BIN
ACTION LOG > 等待指令...
当前算术规则集
\(q_0 \xrightarrow{0/1} R, \quad q_{add} \xrightarrow{Carry} L, \quad q_{return} \xrightarrow{Find \ Y} R\)

“I propose to consider the question, 'Can machines think?' This should begin with definitions of the meaning of the terms 'machine' and 'think.' ... Instead of attempting such a definition I shall replace the question by another, which is closely related to it and is expressed in relatively unambiguous words.

The new form of the problem can be described in terms of a game which we call the 'imitation game.'... We now ask the question, 'What will happen when a machine takes the part of A in this game?' ... These questions replace our original, 'Can machines think?'”

— Alan M. Turing, Computing Machinery and Intelligence (1950)

“我提议考虑一个问题：‘机器能思考吗？’这应当从定义‘机器’和‘思考’的含义开始……但我不打算进行这样的定义，而是用另一个问题来取代它。这个问题与原问题密切相关，并且能用相对清晰的词语来表达。

这个问题的新形式可以通过一个游戏来描述，我们称其为‘模仿游戏’……现在我们要问：‘当一台机器在这个游戏中扮演A的角色时，会发生什么？’……这些问题取代了我们最初的‘机器能思考吗？’”