第3章：丘奇-图灵论题（The Church-Turing Thesis）
一、导读
1.1 本章学习目标
第3章介绍图灵机——计算理论中最核心的模型。图灵机定义了"可计算"的概念，丘奇-图灵论题认为图灵机可以模拟任何有效的计算过程。
1.2 为什么第三章如此重要
图灵机是理解计算本质的关键。它定义了什么是"可计算的"，什么不是。这直接引出了可判定性问题和计算复杂性理论。
1.3 核心问题引导
图灵机与有限自动机有什么本质区别？
丘奇-图灵论题的含义是什么？
图灵机能模拟任何计算吗？
什么是通用图灵机？
二、核心概念详解
3.1 图灵机的定义
图灵机 = 有限状态控制器 + 无限长纸带 + 读写头
形式定义：$(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$
- Q：有限状态集
- Σ：输入字母表（不含空白符）
- Γ：纸带字母表（包含空白符 ␣）
- δ：转移函数 Q × Γ → Q × Γ × {L, R}
- q₀：起始状态
- q_accept：接受状态
- q_reject：拒绝状态3.2 图灵机示例
设计图灵机识别语言 $L = \{0^{2^n} \mid n \geq 0\}$：
算法：
1. 从左到右扫描，每隔一个 0 划掉一个
2. 如果扫描到只有一个 0，接受
3. 如果扫描到多于一个 0 且数量为奇数，拒绝
4. 回到最左端，重复步骤 13.3 丘奇-图灵论题
丘奇-图灵论题不是一个定理，而是一个论题（thesis）：
任何直觉上"可计算的"函数都可以被图灵机计算。
这意味着图灵机是计算能力的上界——没有任何计算模型（包括现代计算机）能超越图灵机的计算能力。
3.4 通用图灵机
通用图灵机（UTM）是可以模拟任何其他图灵机的图灵机：
UTM 的输入：
<M> # w
其中 <M> 是图灵机 M 的描述，w 是输入字符串
UTM 模拟 M 在 w 上的运行这就是现代计算机的理论基础——计算机是一个通用图灵机，可以运行任何程序。
3.5 可编程图灵机
图灵机可以被编码为字符串，这意味着：
图灵机本身可以作为另一个图灵机的输入
可以构造"分析其他图灵机的图灵机"
这为可判定性理论奠定了基础
三、实战案例
3.1 图灵机模拟
python
class TuringMachine:
def __init__(self, states, alphabet, tape_alphabet, transitions,
start_state, accept_state, reject_state):
self.states = states
self.alphabet = alphabet
self.tape_alphabet = tape_alphabet
self.transitions = transitions
self.start_state = start_state
self.accept_state = accept_state
self.reject_state = reject_state
def run(self, input_string):
tape = list(input_string) + ['␣'] * 100
head = 0
state = self.start_state
while state not in (self.accept_state, self.reject_state):
symbol = tape[head]
key = (state, symbol)
if key not in self.transitions:
return False
new_state, new_symbol, direction = self.transitions[key]
tape[head] = new_symbol
state = new_state
if direction == 'R':
head += 1
elif direction == 'L':
head = max(0, head - 1)
return state == self.accept_state
# 示例：识别 0^n1^n
transitions = {
('q0', '0'): ('q1', 'X', 'R'), # 标记第一个 0
('q1', '0'): ('q1', '0', 'R'), # 跳过中间的 0
('q1', '1'): ('q2', 'Y', 'L'), # 标记对应的 1
('q2', '0'): ('q2', '0', 'L'), # 回退
('q2', 'Y'): ('q2', 'Y', 'L'),
('q2', 'X'): ('q3', 'X', 'R'), # 检查是否还有未匹配的 0
('q3', 'Y'): ('q3', 'Y', 'R'),
('q3', '␣'): ('q_accept', '␣', 'R'),
}3.2 图灵可计算函数
python
# 图灵机可以计算任何可计算函数
# 示例：加法
def turing_add(m, n):
"""用图灵机计算 m + n
输入：1^m 0 1^n（一元表示）
输出：1^(m+n)
"""
tape = ['1'] * m + ['0'] + ['1'] * n + ['␣']
# 将 0 替换为 1，删除末尾的 1
# ...
return m + n四、本章小结
第3章介绍了图灵机和丘奇-图灵论题：
图灵机：有限状态 + 无限纸带，是最强大的计算模型。
丘奇-图灵论题：任何直觉上可计算的函数都可以被图灵机计算。
通用图灵机：可以模拟任何其他图灵机，是现代计算机的理论基础。
可编程图灵机：图灵机可以被编码为字符串，为可判定性理论奠定基础。
图灵机定义了计算的上界。理解了图灵机，就理解了"什么是可计算的"。
五、思考与练习
图灵机比有限自动机强大在哪里？
丘奇-图灵论题能被证明吗？
通用图灵机与现代计算机有什么关系？
图灵机的纸带为什么必须是无限的？
有哪些计算模型与图灵机等价？