Turing Machine

Mathematician	Work	Description
Alonzo Church	Lambda Calculus	lambda calculus: a formal system for expressing computation through function abstraction and application
Emil Post	Post Systems	Post correspondence problem: a decision problem in formal language theory
Alan Turing	Turing Machine	Turing machine: a mathematical model of computation with an infinite tape and a read-write head

Turing Machine

图灵机模型是 1936 年由 Turing 提出，用来形式化“算法”这一直观概念；Church 的 λ-演算给出了另一种等价的形式化，二者在可计算能力上是等价的，这一事实形成了 Church–Turing Thesis，主张“可由有效算法完成的计算 = 可由图灵机完成的计算”。

Definition: A Turing Machine is a 7-tuple \((Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})\) where \(Q\), \(\Sigma\), \(\Gamma\) are all finite sets and:

1. \(Q\) is the set of states,
2. \(\Sigma\) is the input alphabet not containing the blank symbol \(\sqcup\),
3. \(\Gamma\) is the tape alphabet, where \(\sqcup \in \Gamma\) and \(\Sigma \subseteq \Gamma\),
4. \(\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}\) is the transition function,
5. \(q_0 \in Q\) is the start state,
6. \(q_{accept} \in Q\) is the accept state, and
7. \(q_{reject} \in Q\) is the reject state, where \(q_{reject} \neq q_{accept}\).

转移函数 \(\delta\) 决定“读 -> 写 -> 移动 -> 变更状态”的一步动作。

Configuration

Definition: A configuration of a TM consists of

• the current state,
• the current tape contents,
• the current head location.

we define a configuration \(u, q, v\), where

• the current state is \(q\),
• the current tape contents is \(uv\), and
• the current head location is the first symbol of \(v\),
• the tape contains only blanks following the last symbol of \(v\).

Example:

        q7
        |
1 0 1 1 0 1 1 1 1 _ _ _ ...

configuration: 1011 \(q_7\) 01111

Formal Definition of Computation

Let \(a, b, c \in \Gamma\), \(u, v \in \Gamma^*\), and \(q_i, q_j \in Q\).

1. If \(\delta(q_i, b) = (q_j, c, L)\), then \[ua\ q_i\ bv \text{**yields**} $u\ q_j\ acv\]
2. If \(\delta(q_i, b) = (q_j, c, R)\), then \(ua\ q_i\ bv\) yields \(uac\ q_j\ v\).

Special cases occur when the head is at one of the ends of the configuration:

1. Left-hand end: The configuration \(q_i\ bv\) yields \(q_j\ cv\) if the transition is left-moving (because we prevent the machine from going off the left-hand end of the tape), and it yields \(c\ q_j\ v\) for the right-moving transition.
2. Right-hand end: The configuration \(ua\ q_i\) is equivalent to \(ua\ q_i\ \sqcup\) because we assume that blanks follow the part of the tape represented in the configuration.

Special Configurations

• 起始格局：在输入串 \(w\) 上运行时，起始格局写作 \(q_0 w\)（读头在输入最左端，其他格全为空白）。
• 接受格局：状态为 \(q_{\text{accept}}\)。
• 拒绝格局：状态为 \(q_{\text{reject}}\)。

接受与拒绝格局都是停机格局，不会再产生后继格局。

Acceptance, Recognition, Decidability

Definition: A TM \(M\) accepts input string \(w\) if there are sequence of configurations \(C_1, C_2, \dots, C_k\) such that:

• \(C_1\) is the initial configuration on input \(w\),
• Each \(C_i\) yields \(C_{i+1}\) according to the transition function,
• \(C_k\) is an accepting configuration.

Language: The collection of strings that \(M\) accepts is the language of \(M\), or the language recognized by \(M\), denoted \(L(M)\).

Definition: A language \(L\) is Turing-recognizable if there exists a TM \(M\) that \(M\) recognizes \(L\).

On an input, the machine M may accept, reject, or loop. By loop we mean that the machine simply does not halt.

If M always halts, then it is a decider. A decider that recognizes some language is said to decide that language.

Definition: A language is Turing-decidable or simply decidable if some Turing machine decides it.

NoteExample 1: \(A = \{ 0^{2^n} \mid n \geq 0 \}\)

stateDiagram-v2
    direction LR
    [*] --> q1
    q1 --> q2: 0/⊔,R
    q1 --> qreject: ⊔/⊔,R
    q2 --> qaccept: ⊔/⊔,R
    q2 --> q3: 0/x,R
    q3 --> q3: x/x,R
    q3 --> q4: 0/0,R
    q3 --> q5: ⊔/⊔,L
    q4 --> q4: x/x,R
    q4 --> q3: 0/x,R
    q5 --> q5: 0/0,L
    q5 --> q5: x/x,L
    q5 --> q2: ⊔/⊔,R
    
    qaccept --> [*]

NoteExample 2: \(B = \{\, w \# w \mid w \in \{0,1\}^* \,\}\)

stateDiagram-v2
  direction LR

  [*] --> q0

  %% q0: 在 # 左侧找第一个未处理符号；用 X 标记左侧的 0，用 Y 标记左侧的 1
  q0 --> qGoHash0: "0 → X, R"
  q0 --> qGoHash1: "1 → Y, R"
  q0 --> q0: "X/Y → 同写, R"
  q0 --> qCheckR: "# → 同写, R"
  q0 --> qReject: "_ → 同写, S"  %% 空输入：不含 #

  %% 向右走到 #（若找不到则拒绝）
  qGoHash0 --> qGoHash0: "0/1/X/Y → 同写, R"
  qGoHash0 --> qMatch0: "# → 同写, R"
  qGoHash0 --> qReject: "_ → 同写, S"

  qGoHash1 --> qGoHash1: "0/1/X/Y → 同写, R"
  qGoHash1 --> qMatch1: "# → 同写, R"
  qGoHash1 --> qReject: "_ → 同写, S"

  %% 在 # 右侧找对应的未处理符号；用 a 标记右侧匹配到的 0，用 b 标记右侧匹配到的 1
  qMatch0 --> qMatch0: "a/b → 同写, R"
  qMatch0 --> qBack: "0 → a, L"
  qMatch0 --> qReject: "1/#/_ → 同写, S"

  qMatch1 --> qMatch1: "a/b → 同写, R"
  qMatch1 --> qBack: "1 → b, L"
  qMatch1 --> qReject: "0/#/_ → 同写, S"

  %% 回到最左端，再进入 q0 继续处理下一个符号
  qBack --> qBack: "0/1/X/Y/a/b → 同写, L"
  qBack --> qToLeftEnd: "# → 同写, L"

  qToLeftEnd --> qToLeftEnd: "0/1/X/Y → 同写, L"
  qToLeftEnd --> q0: "_ → 同写, R"

  %% 左侧处理完后（读到 #），检查右侧是否只剩 a/b，且没有额外的 # 或未处理的 0/1
  qCheckR --> qCheckR: "a/b → 同写, R"
  qCheckR --> qReject: "0/1/# → 同写, S"
  qCheckR --> qAccept: "_ → 同写, S"

  qAccept --> [*]
  qReject --> [*]

Common Design Techniques

在手工设计图灵机时，常用策略包括：

• 反复“对消”(cross-off)：逐步匹配两个区域的符号（如 \(w \# w\) 的比较）。
• 多阶段扫描：从左到右标记、再回到开头、再扫描，模拟计数或配对关系。
• 之字形 (zig-zag) 比较：在纸带上来回移动头部，模拟同时访问“两个指针”。
• 辅助记号：通过覆盖带上符号（写 x 或空白）来“记住”已经处理的位置。

Variants of Turing Machines

FA vs TM: Key Differences

	FA	TM
写能力	只读输入	可读写带上任何位置
头移动	只能右移	左移或右移
带长度	输入长度（有限）	无限（右端可无限延伸）
停机	读完输入后才判定	可在任何时刻立即接受/拒绝

NoteExample: \(C = \{a^i b^j c^k \mid i \times j = k,\; i,j,k \geq 1\}\)

TM \(M\) 的算法：

1. 扫描输入，检查是否形如 \(a^+ b^+ c^+\)，否则拒绝
2. 将头移回最左端的 \(a\)
3. 划掉一个 \(a\)，然后对每个 \(b\)：
   • 将头移到 \(c\) 区域，划掉一个 \(c\)
   • 然后回到 \(b\) 区域的下一个 \(b\)
4. 当一轮 \(b\) 全部扫完后，恢复所有 \(b\) 的标记，再划掉下一个 \(a\)，重复步骤 3
5. 当所有 \(a\) 都被划掉后，检查 \(c\) 区域是否也全部被划掉：
   • 若是，接受（\(i \times j = k\)）
   • 若否，拒绝

空间只需 \(O(n)\)（输入带本身），时间 \(O(n^2)\)。

NoteExample: \(E = \{\#x_1\#x_2\# \cdots \#x_l \mid x_i \in \{0,1\}^*,\; x_i \neq x_j \text{ for } i \neq j\}\)

TM \(M\) 的算法（zig-zag 比较）：

1. 在最上层循环中，对每一对 \((x_i, x_j)\)（\(i < j\)）做比较
2. 比较 \(x_i\) 和 \(x_j\)：将头放在 \(x_i\) 的第一个符号上，做标记，然后移到 \(x_j\) 的第一个符号，做标记并比较
3. 来回移动头部（zig-zag），逐符号比较两个子串
4. 若发现任何一对 \(x_i = x_j\)，立即拒绝
5. 若所有对都不同，接受

Multitape TM

一个多带图灵机具有若干条纸带，每条带有自己独立的读写头：

1. 输入最初放在第 1 条带上，其余带子最初为空白。
2. 在一次转移中，机器同时读取每条带当前格的符号，写回（可能不同的）符号到这些格，更新状态，并为每个带头给出移动方向（左/右/停）。形式化地，若有 \(k\) 条带，则转移函数是

\[ \delta : Q \times \Gamma^k \to Q \times \Gamma^k \times \{L,R,S\}^k . \]

这意味着“同时读、同时写、同时移动 \(k\) 个头”。

重要定理：任意多带图灵机都与某个单带图灵机等价，即它们识别（乃至判定）完全相同的语言类。

NoteProof: Multitape to Single-tape

构造单带 TM \(S\) 模拟 \(k\)-带 TM \(M\)。\(S\) 的带上存储所有 \(k\) 条带的内容，用 \(\#\) 分隔，带点符号 \(\dot{d}\) 标记各虚拟头位置。\(S\) 模拟 \(M\) 的一步：(1) 扫描全带，收集各带头符号；(2) 按 \(M\) 的 \(\delta\) 更新；(3) 再次扫描，写入并移动各带点；(4) 若头越界，右移 \(\#\) 插入空白。若 \(M\) 运行 \(t\) 步，\(S\) 总计 \(O(t^2)\)。Q.E.D.

证明思路：用单带机在一条带上串联地编码所有多带带面的内容，用特殊分隔符（如 #）分割各带内容，并在字符上加“点”来标记每条带头的位置。单带机通过扫描整条带来模拟多带机的一步。

含义：引入更多带子可以极大地简化程序设计与证明复杂性上界，但在“能计算什么”这个层面并不会增强能力。

Nondeterministic TM

Definition: NTM 的转移函数为 \(\delta: Q \times \Gamma \to \mathcal{P}(Q \times \Gamma \times \{L, R\})\)，即对给定状态和带符号，允许多种后继动作。NTM 接受当且仅当至少存在一条计算分支到达 \(q_{\text{accept}}\)。

Theorem: 非确定性并不增加图灵机的计算能力——每个 NTM 都有等价的 DTM。

更具体地，可以构造一个确定性的多带 TM 去系统地枚举并模拟所有非确定性分支。例如，使用第 1 条带保存输入，第二条带作为“当前分支的模拟带”，第三条带记录所做的分支选择（相当于“指令脚本”）；当一种分支模拟要么拒绝，要么走不通，就在第三条带上写下“下一种选择”并重试另一分支。若某分支进入接受配置，则整体接受。

由此得到推论：

• 一个语言是图灵可识别，当且仅当它被某台非确定性图灵机识别。
  
• 一个语言是可判定的，当且仅当它被某台在所有分支上必定停机的非确定性图灵机判定。

Enumerator

graph LR
    subgraph enum["Enumerator"]
        TM["TM M"]
        Printer["Printer"]
    end
    TM -->|"outputs strings"| Printer

“递归可枚举语言”这个名字来自于枚举器 (enumerator) 这一等价模型。枚举器可以被看作一台带有打印机的图灵机；该图灵机可以把任意字符串送到打印机，以此“枚举”一系列字符串。形式上：

• 枚举器按某种顺序输出若干字符串。
• 我们把它输出的所有字符串的集合称为它“枚举”的语言。

核心定理：某语言是图灵可识别，当且仅当存在一个枚举器能枚举它。

证明思路（双向）：

• 若有枚举器 \(E\) 输出某语言 \(A\)，要判断输入 \(w\) 是否在 \(A\)：并行地运行 \(E\)，一旦 \(E\) 打印出 \(w\) 就接受。
• 反之，若有 TM \(M\) 识别 \(A\)，则可按长度次序列举所有可能字符串 \(s_1,s_2,s_3,\dots\)，并交错模拟 \(M\) 在这些串上的运行：每当发现某个 \(s_j\) 被接受，就把 \(s_j\) 打印出来。

枚举器等价性说明：“能被 TM 识别”与“能被系统地产出（列举）”是一回事。这是理解“半判定 (semi-decision)”或“半可判定”概念的另一种角度。

在这里，有一道习题的讨论

Church–Turing Thesis 与算法的本质

历史动机：Hilbert 在 1900 年提出一系列著名公开问题，其中第十个问题要求设计算法，判定给定整系数多元多项式是否存在整数根。他的表述是希望找到“一种在有限步操作内可确定答案的程序化过程”，也就是现代意义下的判定算法。

1936 年，Church 用 λ-演算给出的“可计算函数”，Turing 用图灵机给出的“可计算过程”，都试图形式化“算法”这一直觉，并最终被证明等价。这催生了 Church–Turing Thesis：任意“有效可实现的算法”都可以由图灵机实现，反之图灵机能做的都属于可计算的范围。

该思想立即带来一个深刻结论：某些问题根本没有判定算法。例如，给定一个多项式 \(p(x)\)（单变量整系数），判定它是否存在整数根，其语言 \[ D_1 = \{\, p \mid p \text{ 是单变量整系数多项式且存在整数根} \,\} \]

事实上是可判定的（可在有穷搜索上给出上界），而更一般的多元情形 \[ D = \{\, p \mid p \text{ 是整系数多元多项式且存在整数根} \,\} \]

在 1970 年被证明不可判定，即不存在图灵机判定器。

Church–Turing Thesis 让我们把“可计算”和“图灵可计算”视为同义，从而以图灵机为基准来研究“判定性 (decidability)”“可识别性 (recognizability)”以及“不可判定性 (undecidability)”。这为后续“Decidability”一章奠定基础。

Church–Turing Thesis

We call it Church–Turing Thesis because it can not be proven, but it is a very important idea in computer science:

Church–Turing Thesis: Any “effectively calculable function” can be computed by a Turing machine.

Hilbert’s Tenth Problem

Hilbert’s Tenth Problem(also known as Diophantine Equation Problem) can be rewrited into whether a language \(D\) is decidable:

\[ D = \{p | p \text{ is a polynomial with integer coefficients and has integer roots}\} \]

Four TCS scientists have shown that \(D\) is undecidable.

NoteProof

We can define a simpler language \(D_1\):

\[ D_1 = \{p | p \text{ is a polynomial on a single variable x with integer coefficients and has integer roots}\} \]

Lemma 1: Both \(D\) and \(D_1\) are Turing-recognizable.

Proof 1: Construct a process: On input \(p(x)\), evaluate \(p\) with \(x\) set successively to \(0, 1, -1, 2, -2, \dots\). If \(p(x) = 0\) for some \(x\), accept. Above process can be implemented by a TM.

Lemma 2: Let \(p(x) = c_1x^n + c_2x^{n-1} + \dots + c_nx + c_{n+1}\) with \(c_1 \neq 0\) and \(p(x_0) = 0\). Define \(c_{max} = \max \{|c_i|\}_{i \in [n+1]}\). Then \[|x_0| < \frac{c_{max}(n+1)}{|c_1|}\]

NoteProof of Lemma 2

Proof: Since \(p(x_0) = 0\), we have: \[c_1x_0^n + c_2x_0^{n-1} + \dots + c_nx_0 + c_{n+1} = 0\]

Rearranging: \[c_1x_0^n = -(c_2x_0^{n-1} + c_3x_0^{n-2} + \dots + c_nx_0 + c_{n+1})\]

Taking absolute values: \[|c_1||x_0|^n = |c_2x_0^{n-1} + c_3x_0^{n-2} + \dots + c_nx_0 + c_{n+1}|\]

By triangle inequality: \[|c_1||x_0|^n \leq |c_2||x_0|^{n-1} + |c_3||x_0|^{n-2} + \dots + |c_n||x_0| + |c_{n+1}|\]

Since \(|c_i| \leq c_{max}\) for all \(i\): \[|c_1||x_0|^n \leq c_{max}(|x_0|^{n-1} + |x_0|^{n-2} + \dots + |x_0| + 1)\]

If \(|x_0| \geq 1\), then \(|x_0|^{n-1} + |x_0|^{n-2} + \dots + |x_0| + 1 \leq n|x_0|^{n-1} + 1 \leq (n+1)|x_0|^{n-1}\).

Thus: \[|c_1||x_0|^n \leq c_{max}(n+1)|x_0|^{n-1}\]

Dividing both sides by \(|c_1||x_0|^{n-1}\) (valid since \(c_1 \neq 0\) and \(x_0 \neq 0\)): \[|x_0| \leq \frac{c_{max}(n+1)}{|c_1|}\]

If \(|x_0| < 1\), the bound trivially holds.

Q.E.D.

Corollary: \(D_1\) is decidable. (Because it is finite, so we can enumerate all possible roots and check if any of them is a root of \(p(x)\).)

Then prove the D by contradiction:

1. Assume \(D\) is decidable. Then there exists a Turing machine \(M_D\) that decides \(D\).

2. Construct a computable function \(f\) that maps any Turing machine \(M\) and input \(w\) to a polynomial \(p(x)\) such that:

   • \(M\) halts on \(w\) iff \(p(x)\) has rational roots.
   • \(M\) does not halt on \(w\) iff \(p(x)\) has no rational roots.

   This step (constructing f) is completed by those TCS scientists in 1970s.

3. If \(D\) were decidable, we can decide the halting problem by

   • Given \((M, w)\), compute \(p(x)\) using \(f(M, w)\).
   • Run \(M_D\) on \(p(x)\).
   • If \(M_D\) accepts \(p(x)\), accept \((M, w)\).
   • If \(M_D\) rejects \(p(x)\), reject \((M, w)\).

4. Contradiction: \(M_D\) decides \(D\), and \(M_D\) decides the halting problem, which is undecidable.