第十五课：语言识别、图灵机、哥德尔不完备定理

图灵机

基本模型

• 无限长的磁带（存储介质）
• 读写头（可以读、写、左移、右移）
• 有限状态控制器
• 转移函数：根据当前状态和读到的符号，决定：
• 写什么新符号
• 往哪个方向移动
• 进入哪个新状态

图灵机识别语言

• 初始：输入字符串写在磁带上，读写头在开头
• 过程：根据转移函数逐步执行
• 终止：进入接受状态或拒绝状态
• 图灵机可识别的语言 = 递归可枚举语言

构造例子

• 识别L={aᵐbᵐ | m≥0}的图灵机
• 基本思路：配对消除——标记一个a和一个b，重复直到所有字符被配对

停机问题 ⭐

问题的提出

• 是否存在一个算法，能判定任意图灵机对任意输入是否停机？

不可判定性证明

• 假设存在判定停机问题的图灵机H
• 构造新的图灵机D：如果H说"停机"，D就进入死循环；如果H说"不停机"，D就停机
• 将D自身作为输入送给D→产生悖论
• ∴ 不存在这样的判定算法

💡 人话：停机问题证明了"不能写一个程序判断任意程序是否会死循环"。证明方法和"这句话是错的"这种自指悖论一样——让程序判断自己。

哥德尔不完备定理

核心结论

• 任何包含自然数定义的形式系统，要么不完备，要么不一致
• 不完备：存在真命题但无法在系统中证明
• 不一致：系统内部自相矛盾

与计算机科学的关系

• 揭示了形式系统的根本局限
• 数学不能证明所有真理
• 最终的计算模型（图灵机）也存在固有的不可判定问题

💡 人话：哥德尔证明了数学不是万能的——不管你怎么选公理，总有一些真的数学命题你证不出来。这就是为什么希尔伯特"用数学证明数学本身是完美的"梦想实现不了。