离散数学(18) 陈斌 gischen@pku.edu.cn 2009.12.25

目录 数理逻辑、集合论、图论、抽象代数 形式语言和自动机 语言和对语言的研究 形式语言的语法表示 有限状态自动机 机器化简和运算实现 停机问题与哥德尔不完全定理

图灵机Turing Machine si 基本结构 一条分格的无限长的纸带，每格可容纳一个字符 一个读写头，可以在纸带上移动，读出当前格子的字符，重写格子上的内容，改变自己的内部状态 一系列关于读写头动作的规则（程序） a3 a2 a1 B ai ai+1 a4 B a1 a0 si

图灵机 输入、计算和输出 纸带上的内容（包括空白B）是计算前的输入和计算完成后的输出 计算从读写头的初始状态s0、初始位置和输入的纸带格局开始 按照规则进行读写头的移动、纸带字符的修改，直到进入停机状态（SH/SY/SN） 在停机状态时纸带的内容就是输出

图灵机 计算规则 规则q={si,ak,al,sj,d}，si,sj∈S（内部状态），ak,al∈A（纸带字符），d∈{L,R,N}（左移，右移，不动） 表示如果读写头当前状态为si，读到当前格子字符为ak，则： 改写格子内容为al 转变状态为sj 进行d指定的动作（读写头左移、右移或不动）

图灵机 计算规则的限制 形式语言与图灵机 有限条规则 任意两条规则前两项不能相同 没有规则第一项是SH/SY/SN 动作的确定性 没有规则第一项是SH/SY/SN 保证这三个状态是停机状态 形式语言与图灵机 当WA*，将W中的任意字符串w作为输入，M都停止在接受状态SY，A-W的字符串M停止在拒绝状态SN或者永不停机，称M接受/识别语言W=L(M) 形式语言L能被图灵机M识别，当且仅当L是一个0型形式语言

图灵机例子：ambm W={ambm|m>=0} 思路：将a和b一一对消，如果最后剩下空白则接受，否则拒绝 s0, a, B, s1, R：初始碰到a，消去，s1，右移 s1, a, a, s1, R：消去1个a的状态，继续右移，找最后一个b s1, b, b, s1, R：继续右移 s1, B, B, s2, L：右移到头状态s2，回移 s2, b, B, s3, L：如果有b，消去，进入左移状态s3 s3, b, b, s3, L：左移 s3, a, a, s3, L：左移

图灵机例子：ambm 识别规则 s3, B, B, s0, R：左移到头变初始状态，右移看下个字符 s0, B, B, sY, N：a,b都能一一消完，则接受 s0, b, b, sN, R：b多了，或者在a前，拒绝 s2, a, a, sN, R：a多了，或者在b后，拒绝 s2, B, B, sN, R：a多了，拒绝

识别与判定 识别： 枚举： 判定： 只有L和L的补语言都是图灵可识别的情况下，L才是图灵可判定的。 存在语言是图灵机可识别但不可判定的 属于语言的串在有限步被接受，不属于语言的串被拒绝或者永不停机 枚举： 枚举生成所有属于语言的串，对于无限集合语言，这个生成过程可能永不停止，可识别＝可枚举 判定： 属于语言的串被接受，且不属于语言的串被拒绝 只有L和L的补语言都是图灵可识别的情况下，L才是图灵可判定的。 存在语言是图灵机可识别但不可判定的 和停机问题相关

图灵机例子：加法运算 表示自然数 表示二元参数 f(m,n)=m+n：即字符串的连接操作 f(m,n)=m*n：即将m重复copy n次 用n+1个连续的1表示自然数n 0＝1，1＝11，2＝111，3＝1111…… 表示二元参数 两个输入的自然数之间用B隔开 0，2＝1B111 f(m,n)=m+n：即字符串的连接操作 f(m,n)=m*n：即将m重复copy n次

图灵机的变种 具有k条纸带的图灵机 双向无界的图灵机 非确定性图灵机 所有这些计算能力都相同，可以归结到等价的确定性单纸带图灵机 k条纸带，k个读写头 双向无界的图灵机 左边、右边都无限制增长 非确定性图灵机 计算规则的前两项可以相同，机器任意选择一个分支进行 规则必须一致，禁止一个分支导致接受而另一个分支导致拒绝 所有这些计算能力都相同，可以归结到等价的确定性单纸带图灵机

可计算函数 函数f:NN是可计算的，如果存在一个图灵机M使得对每个自然数n停机，输出为f(n) 可计算函数＝递归函数 如果f,g都是可计算的，那么复合函数h=g°f也是可计算的 推广到多元函数 可计算函数＝递归函数 保证能停机并得到结果 原始递归函数包括了多数可形式化的计算 从0函数、后继函数、投影函数进行有限次的复合、原始递归 h(0)=f(x), h(n+1)=g(h(n),n,x)

可计算函数与图灵可计算函数 存在非原始递归的可计算函数 可计算函数图灵可计算函数 简单但恐怖的递归函数Ackermann 存在图灵可计算但不是递归函数，和停机问题相关 不能判定是否一定停机的图灵机

Ackermann函数

哥德尔编码Gödel Numbering 将任何形式语言L编码为自然数的集合 哥德尔编码过程 将语言上的运算变换为自然数的运算 形式系统的问题变换为数论问题 还记得命题演算、谓词演算？ 哥德尔编码过程 定义p(n)=第n个素数，n>0 我们知道素数有无限个 任何正整数都能唯一地写成素数的乘积 LA*，A={a1,a2,…an}，任意w={am1am2..amk}∈L G(w)=i=1kp(i)mi

哥德尔编码 A={a,b,c,d} G(‘accdbdd’)=21*33*53*74*112*134*174 =4,677,894,230,215,956,750 重要结论：如果字母表A是可数的，则A上的所有形式语言L都是可数的

通用图灵机Universal TM 程序和通用计算机 通用图灵机 每个程序执行特定的计算 但我们的计算机可以执行所有的程序，并得到相同的结果 通用计算机是一种特别的程序，将程序和程序的输入作为其输入，输出程序的输出 通用图灵机 每个图灵机计算特定的函数，识别特定的语言 能否有一个通用图灵机，能模拟任意图灵机的执行，对相应的输入得到相应的结果呢？

通用图灵机 图灵机的编码 输入、输出的编码 图灵机的定义包含有限字符集A、有限状态集S和读写头的运动规则 对图灵机的描述就是一个A∪S∪{L,R,N}上的字符串 将这个字符串进行哥德尔编码，得到哥德尔数G(M) 输入、输出的编码 对图灵机的输入、输出是A上的字符串，也可以进行哥德尔编码

通用图灵机 通用图灵机U存在 有趣的是，U本身也可以进行哥德尔编码，作为输入参数在U中进行计算 接受两个输入整数a, k 计算结果是M(a)在输入I(k)下的输出结果的哥德尔数G(o) U所计算的函数是U(a,k)N 有趣的是，U本身也可以进行哥德尔编码，作为输入参数在U中进行计算 可以产生能够自我复制的图灵机

停机问题Halting Problem 一个实际问题： 对于特定的算法，我们大概是可以判定的，但是否存在对一般的算法进行判定的方法？ 给定一个算法和相应的输入，判定这个算法是否能够完成？（还是进入死循环不能完成？） 由于算法都可以用图灵机描述，所以问题转变为，给定一个图灵机和相应的输入，判定是否停机？ 对于特定的算法，我们大概是可以判定的，但是否存在对一般的算法进行判定的方法？ 程序正确性证明：包括了给一段程序，判断这段程序是否会进入死循环 注意：这个方法本身也是一个算法，否则没有意义

停机问题 是否有算法能够判定某个图灵机M在输入I下是否停机？ 即Halt(M,I)=True iif M在I处停机，False iif M在I处不停机 答案是否定的，不存在这样的算法 停机问题是不可计算问题

停机问题证明 假设存在这样的算法，对应的图灵机是Halt(a,k)，a是要判定的图灵机编码，k是输入的编码 我们构造这么一个图灵机Trouble(a) function Trouble(a) if Halt(a, a) = False then return True else loop forever Trouble图灵机自然也可以编码，记为t，我们来看把t作为Trouble输入会怎么样？ Trouble(t)=?

停机问题证明 矛盾？矛盾！ 消除矛盾的唯一途径就是否定假设，即不存在能一般性地判定图灵机停机的算法 如果Trouble(t)停机返回了，也就是Halt(t,t)=False，但这样是说Trouble(t)不停机，矛盾 如果Trouble(t)不停机，也就是Halt(t,t)返回了True，但这样却是说Trouble(t)能停机，矛盾 消除矛盾的唯一途径就是否定假设，即不存在能一般性地判定图灵机停机的算法 人的智能就能解决停机问题么？至少目前还是否 对于太长的算法，或者输入太复杂的算法，不能 对于一些短而简单的算法，也不能（一些数论难题） 寻找大于给定N的孪生素数

哥德尔不完备定理 任何包含自然数定义的形式系统都是不完全的，也就是存在不能证明为真也不能证明为假的命题 证明和计算 重点是证明，一个开始于公理，结束于此命题的公理-定理有限序列 也就是，系统可能存在一些命题，它们是定理，却无法给出证明序列 证明和计算 可证明 v.s. 计算停机 不可判定的命题 v.s. 永不停机的计算

哥德尔不完备定理的证明 形式系统的哥德尔编码 将符号系统用自然数编号 所有的命题和谓词看成是符号系统上的字符串 得到所有命题和谓词的哥德尔数 命题序列也进行编码GN=2GN1*3GN2*5GN3 Statement 1 (GN1) Statement 2 (GN2) Statement 3 (GN3) 如果一个序列是一个命题的证明，我们可以写谓词R(v,x)，x是序列的哥德尔数，v是命题的哥德尔数

哥德尔不完备定理的证明 我们来看： 不一致的系统完全不可以接受，所以我们只能接受系统不完备这个事实 xR(v,x)：v不可证明 这个谓词对应的哥德尔数记做GN4 考察：xR(GN4,x)：本命题不可证明 这是一个命题，具有确定的真值，但是否可证明呢？ 如果可证明，那么就是证明了一个假命题，系统不一致了 如果不可证明，那就是一个真命题，是一个定理，却不能证明，系统不完备 不一致的系统完全不可以接受，所以我们只能接受系统不完备这个事实

停机问题和哥德尔不完备定理 两个不同领域的不可判定问题 得到相似的结论 形式化的缺陷？人类思维的局限？ 数理逻辑 计算理论 没有一个“万能”的公理系统，在其中能够证明所有的数学真理，而排除谬误 没有一个“万能”的算法，能够判定所有的算法是可以完成，还是陷入无限循环 形式化的缺陷？人类思维的局限？ 自我吞噬的怪圈才是产生智能的基础？

不可判定问题的意义？ 人类推理和知识的极限？ 终极理论的命运？ 人工智能的极限？ 如何研究复杂系统？ 只通过形式系统不能达到所有的真理？ 是否有统一描述宇宙的理论？ 人工智能的极限？ 机器的智能能否超越人类思维？ 如何研究复杂系统？ 元胞自动机：简单的规则，复杂的行为 生命？ 自组织现象？

参考文献 离散数学，许蔓苓编著，北京航空航天大学出版社 离散数学，[美]S.利普舒尔茨 M.利普森著，科学出版社

END 特殊符号表 ∴,∵,╞═╡,╞═,∈,≠,∑,↓,∪,∩,╞,┠PC αΑ,βΒ,γΓ,δΔ,εΕ,ζΖ,ηΗ,θΘ,ιΙ,κΚ,λΛ,μΜ,νΝ,ξΞ,οΟ,πΠ,ρΡ,ς΢,σΣ,τΤ,υΥ,φΦ,χΧ,ψΨ,ωΩ {¬,∧,∨,→,↔} ≦≧≠≤ø 