《丘奇-图灵论题》由会员分享，可在线阅读，更多相关《丘奇-图灵论题（66页珍藏版）》请在金锄头文库上搜索。
1、朴秀峰朴秀峰计算理论1引言q什么是计算？什么是计算？q计算机的基本能力和局限性是什么？计算机的基本能力和局限性是什么？2引言计算机科学历史上关于概念的争论计算机科学历史上关于概念的争论计算机科学历史上关于概念的争论计算机科学历史上关于概念的争论q什么是计算什么是计算q什么是操作系统什么是操作系统 基本上解决基本上解决基本上解决基本上解决q什么什么internet ?q什么是数据库什么是数据库q什么是数据仓库什么是数据仓库 还在争论还在争论还在争论还在争论q什么是数据网格什么是数据网格q解决方法，解决方法，解决方法，解决方法， 给出大众能理解的代表给出大众能理解的代表给出大众能理解的代表给出大众
2、能理解的代表3引言计算机科学历史上关于概念的争论计算机科学历史上关于概念的争论计算机科学历史上关于概念的争论计算机科学历史上关于概念的争论q解决的办法，解决的办法， 给出一个代表给出一个代表q什么是什么是 3的倍数的倍数 3N |N=1,2,3, x| x mod 3 =0q代表元代表元 ：3 q什么是操作系统什么是操作系统 代表元：代表元：Windows, Unix q什么什么internet 代表元：大众理解：代表元：大众理解：Web ， IE q什么是计算什么是计算? 多个模型；代表元：图灵机多个模型；代表元：图灵机, 或或 递归函递归函数论数论4引言在还没有计算机的时在还没有计算机的时
3、在还没有计算机的时在还没有计算机的时候，候，候，候， 凭想象力凭想象力凭想象力凭想象力把后来把后来把后来把后来出现的出现的出现的出现的 把计算机的理把计算机的理把计算机的理把计算机的理论模型建立起来了。论模型建立起来了。论模型建立起来了。论模型建立起来了。19361936年年年年想得如此周到、严密想得如此周到、严密想得如此周到、严密想得如此周到、严密好像从高度文明的外好像从高度文明的外好像从高度文明的外好像从高度文明的外星来的文化使者星来的文化使者星来的文化使者星来的文化使者5引言Alan M. Turing (19121954)In 1936, Turing introduced hisab
4、stract model for computation inhis article “On Computable Numbers,”.At the same time, Alonzo Church published similar ideas and results. 殊途同归Turing model 成为理论计算科学的标准模型standard modelstandard model6引言q图灵机（图灵机（Turing Machine，TM），是计算机的一种简单的），是计算机的一种简单的数学模型。数学模型。q历史上，冯历史上，冯诺曼计算机的产生就是由图灵机诱发的。诺曼计算机的产生就是由图灵
5、机诱发的。q丘奇丘奇图灵论题：一切合理的计算模型都等同于图灵机图灵论题：一切合理的计算模型都等同于图灵机.7主要内容主要内容3.1 丘奇丘奇图灵论题图灵论题3.1.1 图灵机的形式化定义图灵机的形式化定义3.1.2 图灵机的例子图灵机的例子3.2 图灵机的变形图灵机的变形3.2.1 多带图灵机多带图灵机3.2.2 非确定型图灵机非确定型图灵机3.2.3 枚举器枚举器3.2.4 与其他模型的等价性与其他模型的等价性3.3 算法的定义算法的定义3.3.1 希尔伯特问题希尔伯特问题3.3.2 描述图灵机的术语描述图灵机的术语83.1 图灵机(Turning Machine)非形式化描述非形式化描述非
6、形式化描述非形式化描述根据当前状态和字符根据当前状态和字符 xi ，决定，决定 写写 移移 转转三动作三动作-写写 letter, 有存储器有存储器- 左或右移动左或右移动- 转移状态转移状态 可以作循环语句可以作循环语句磁带相当于数组，可读写。这是增加的重要资源磁带相当于数组，可读写。这是增加的重要资源internal state set QRL每一步，读写头在每一步，读写头在每一步，读写头在每一步，读写头在单向无穷带上左右单向无穷带上左右单向无穷带上左右单向无穷带上左右移动并读写。移动并读写。移动并读写。移动并读写。9图灵机state q0初始初始, 带子上只有输入串带子上只有输入串w*,
7、其它地方是空的。开始状态其它地方是空的。开始状态 q0。计算过程中读写头左右移动，机器内部状态改计算过程中读写头左右移动，机器内部状态改变，带子上内容重写。变，带子上内容重写。数组结构10图灵机输出约定输出约定输出约定输出约定三种输出：接受、拒绝、循环三种输出：接受、拒绝、循环state qacceptstate qrejector非常规意义循非常规意义循环环不停机不停机引出可判定性引出可判定性11图灵机与有限自动机状态状态控制器控制器aab 相似性：有限状态集相似性：有限状态集区别：区别：(1)图灵机在带子上图灵机在带子上既能读也能写既能读也能写。(2)图灵机的图灵机的读写头既能向左也能向右
8、移动读写头既能向左也能向右移动。(3)图灵机的图灵机的带子是无限长的带子是无限长的。(4)图灵机图灵机进入拒绝和接受状体将立即停机进入拒绝和接受状体将立即停机。12图灵机q考虑图灵机考虑图灵机 M1，它检查语言，它检查语言 B = w#w | w0,1* 的成员的成员关系。即设计关系。即设计 M1，使得如果输入是，使得如果输入是 B 的成员，它就接受，的成员，它就接受，否则拒绝。否则拒绝。qM1=“对于输入字符串对于输入字符串 w(1) 在在 # 两边对应的位置上来回移动，检查这些对应位置是两边对应的位置上来回移动，检查这些对应位置是否包含相同的符号，如不是，或者没有否包含相同的符号，如不是，
9、或者没有 #，则拒绝，为，则拒绝，为跟踪对应的符号，消去所有检查过的符号。跟踪对应的符号，消去所有检查过的符号。(2) 当当 # 左边的所有符号都被消去时，检查左边的所有符号都被消去时，检查 # 右侧是否还有右侧是否还有符号，如果有则拒绝，否则接受。符号，如果有则拒绝，否则接受。”13M1 的运行示意图01100#01100 LLX1100#01100 LLX1100#01100 LLX1100#01100 LLMTape head moves to right14M1 的运行示意图X1100#01100 LLX1100#01100 LLX1100#X1100 LLX1100#X1100 LL
10、MTape head moves to left15M1 的运行示意图X1100#X1100 LLX1100#X1100 LLXX100#X1100 LLXX100#X1100 LLMTape head moves to right16M1 的运行示意图XX100#X1100 LLXX100#X1100 LLXX100#XX100 LLXX100#XX100 LLMTape head moves to left17M1 的运行示意图XX100#XX100 LLXX100#XX100 LLXXX00#XX100 LLXXX00#XX100 LLMTape head moves to right1
11、8M1 的运行示意图XXXXX#XXXX0 LLXXXXX#XXXXX LLXXXXX#XXXXX LLMXXXXX#XXXXX LLTape head moves to left19M1 的运行示意图XXXXX#XXXXX LLXXXXX#XXXXX LLXXXXX#XXXXX LLMXXXXX#XXXXX LLacceptTape head moves to right20图灵机的形式化定义定义定义定义定义3.13.1图灵机是一个图灵机是一个 7 元组元组 (Q, , , , q0, qaccept, qreject)(1) Q 是状态集。是状态集。(2) 是输入字母表，不包括特殊空白符号
12、是输入字母表，不包括特殊空白符号 。(3) 是带字母表，其中是带字母表，其中 并且并且 。(4) : Q Q L, R 是转移函数。是转移函数。(5) q0 是起始状态。是起始状态。(6) qaccept 是接受状态。是接受状态。(7) qreject 是拒绝状态，是拒绝状态，qacceptqreject。例如例如 : (q, a) = (r, b, L)21图灵机的计算方式q开始时，开始时，M 以最左边的以最左边的 n 个带方格接收输入个带方格接收输入w=w1w2wn *，带的其余部分保持空白，带的其余部分保持空白(即填以空白符即填以空白符)，读写头从最，读写头从最左边的带方格开始运行，注意
13、左边的带方格开始运行，注意 不含空字符不含空字符，故，故出现在带出现在带上的第一个空字符表示输入的结束上的第一个空字符表示输入的结束。qM 开始运行后，计算根据转移函数所描述的规则进行，如开始运行后，计算根据转移函数所描述的规则进行，如果果 M 试图将读写头从带的最左端再向左移出，即使转移函试图将读写头从带的最左端再向左移出，即使转移函数指示的是数指示的是 L，读写头也停在原地不动。计算一直持续到，读写头也停在原地不动。计算一直持续到它进入接受状态或拒绝状态，此时停机，如果二者都不发它进入接受状态或拒绝状态，此时停机，如果二者都不发生，则生，则 M 将永远运行下去。将永远运行下去。w1w2wn
14、 22图灵机的格局q图灵机计算过程中，图灵机计算过程中，当前状态当前状态、当前带内容当前带内容和和读写头当前读写头当前位置位置组合在一起，称为组合在一起，称为图灵机的格局图灵机的格局。q对于状态对于状态 q 和带字母表和带字母表 的两个字符串的两个字符串 u 和和 v，以，以 uqv 表表示如下格局：当前状态是示如下格局：当前状态是 q，当前带上的内容是，当前带上的内容是 uv，读写，读写头的当前位置是头的当前位置是 v 的第一个符号，带上的第一个符号，带上 v 的字符最后字符的字符最后字符以后的符号都是空白符。以后的符号都是空白符。q 例如，例如，1011q701111101101111 q
15、723图灵机计算方式的形式化q如果图灵机能合法地从格局如果图灵机能合法地从格局 C1 一步进入一步进入 C2，则称格局，则称格局 C1产生产生格局格局 C2。q设设 a, b 和和 c 是是 中的符号，中的符号，u 和和 v 是是 * 中字符串，中字符串，qi 和和 qj是状态，则是状态，则 uaqibv 和和 uqjacv 是两个格局。如果转移函数满是两个格局。如果转移函数满足足 (qi , b) = (qj , c, L)，则说，则说uaqibv 产生和产生和 uqjacv 。qM 在输入在输入 w 上的上的起始格局起始格局是格局是格局 q0w，表示机器处于起始，表示机器处于起始状态状态
16、q0，并且读写头处于带子的最左端位置，在，并且读写头处于带子的最左端位置，在接受格局接受格局里，状态是里，状态是 qaccept ，在，在拒绝格局拒绝格局里，状态是里，状态是 qreject。接受和。接受和拒绝状态都是拒绝状态都是停机状态停机状态，它们都不再产生新的格局。，它们都不再产生新的格局。q由于图灵机只在接受或拒绝状态下才停机，可以等价地将由于图灵机只在接受或拒绝状态下才停机，可以等价地将状态转移函数简化状态转移函数简化 : Q Q L, R 其中其中 Q 是是取消取消 qaccept 和和qreject 的的 Q。24图灵机计算方式的形式化q图灵机图灵机 M 接受输入接受输入 w ，
17、如果存在格局的序列，如果存在格局的序列 Cl, C2, , Ck使得：使得： (1) Cl 是是 M 在输入在输入 w 上的起始格局；上的起始格局； (2) 每一个每一个Ci 产生产生 Ci +1； (3) Ck 是接受格局。是接受格局。qM 接受的字符串的集合称为接受的字符串的集合称为 M 的语言的语言，或被，或被 M 识别的语识别的语言言，记为，记为 L(M)。25图灵机的形式化定义定义定义定义定义3.23.2如果一个语言能如果一个语言能被某一图灵机识别被某一图灵机识别，则称该语言是，则称该语言是图灵可识别的图灵可识别的 (Turning recognizable)。也称为也称为递归可枚举
18、语言递归可枚举语言。 输入上运行一个输入上运行一个TM时，可能出现三种结果：时，可能出现三种结果：接受、拒绝、循环接受、拒绝、循环（仅仅指机器不停机）（仅仅指机器不停机）对于一个输入，对于一个输入，TM有两种方式不接受它：有两种方式不接受它：一种拒绝状态一种拒绝状态一种进入循环一种进入循环问题：如何区别长计算问题：如何区别长计算 与与 死循环？死循环？因此，我们喜欢对所有输入都停机的图灵机，永不循环，这因此，我们喜欢对所有输入都停机的图灵机，永不循环，这因此，我们喜欢对所有输入都停机的图灵机，永不循环，这因此，我们喜欢对所有输入都停机的图灵机，永不循环，这种机器为种机器为种机器为种机器为判定器
19、。因为它们总能决定是接受还是拒绝。判定器。因为它们总能决定是接受还是拒绝。判定器。因为它们总能决定是接受还是拒绝。判定器。因为它们总能决定是接受还是拒绝。26图灵机的形式化定义定义定义定义定义3.33.3如果一个语言能如果一个语言能被某一图灵机判定被某一图灵机判定，则称该语言是，则称该语言是图灵可判定的图灵可判定的 (Turning decidable)。也称为也称为递归语言递归语言。 可识别与可判定？可识别与可判定？1.可识别可识别接受该语言；接受该语言；2.可判定可判定可以不接受该语言。可以不接受该语言。27图灵机举例例例3.4 描述描述 TM M2，它识别的语言是所有由，它识别的语言是所
20、有由 0 组成、长度为组成、长度为 2的方幂的字符串，即的方幂的字符串，即 A= | n 0 M2 = “对于输入字符串对于输入字符串w： 1) 从左往右扫描整个带子，隔一个字符消去一个从左往右扫描整个带子，隔一个字符消去一个0。 2) 如果在第如果在第1步之后，带子上只剩下唯一的一个步之后，带子上只剩下唯一的一个0，则接受。，则接受。 3) 如果在第如果在第1步之后，带子上包含不止一个步之后，带子上包含不止一个0，并且，并且0的个数是的个数是奇数，则拒绝。奇数，则拒绝。 4) 读写头返回至带子的最左端。读写头返回至带子的最左端。 5) 转到第转到第1步。步。”28图灵机举例q1q3q4qre
21、jectq2qacceptq50 , R RxR R0x, RxRxR L0RxR R0x, RxL0L R29图灵机的例子q每重复一次第每重复一次第 1 步，消去了一半个数的步，消去了一半个数的 0。由于在第。由于在第 1 步中，步中，机器扫描了整个带子，故它能够知道它看到的机器扫描了整个带子，故它能够知道它看到的 0 的个数是的个数是奇数还是偶数，如果是大于奇数还是偶数，如果是大于 1 的奇数，则输入中所含的的奇数，则输入中所含的 0 的个数不可能是的个数不可能是 2 的方幂，此时机器就拒绝。但是，如果的方幂，此时机器就拒绝。但是，如果看到的看到的 0 的个数是的个数是 1，则输入中所含的
22、，则输入中所含的 0 的个数肯定是的个数肯定是 2 的方幂，此时机器就接受。的方幂，此时机器就接受。qM2= (Q, , , , q1, qaccept, qreject)的形式化描述：的形式化描述： Q=q1 , q2 , q3 , q4 , q5 , qaccept, qreject， =0， =0 , x , ， 将将 描述成状态图描述成状态图 开始、接受和拒绝状态分别是开始、接受和拒绝状态分别是q1, qaccept, qreject 30图灵机举例例例3.5 下面给出图灵机下面给出图灵机 M1 形式化描述形式化描述M1= (Q, , , , q1, qaccept, qreject)
23、，它的判定语言是它的判定语言是 B = w#w | w 0, 1* 。Q = q1, q2, , q8 , qaccept, qreject ， = 0, 1, # 且且 = 0, 1, #, x, 。用状态图描述用状态图描述 。开始、接受和拒绝状态分别是开始、接受和拒绝状态分别是 q1, qaccept, qreject。31图灵机M1的状态图q1q8q3q5q6q4q7qacceptq2#RxRR0,1R#RxR0,1,xL0,1L#LxR1x,L1x,R0x,L#R0x,R0,1RxR第一步由第一步由q1 到到 q7 实现，实现，第二步由其余状态实现第二步由其余状态实现32图灵机举例例例
24、3.6 图灵机图灵机 M3 做一些初等算术，它判定的语言做一些初等算术，它判定的语言C = aibjck | i j = k，且，且 i, j, k 1M3=“对于输入字符串对于输入字符串 w： 1) 从左往右扫描输入，确认输入具有形式从左往右扫描输入，确认输入具有形式 a*b*c*，否则拒，否则拒绝。绝。 2) 读写头回到带子的左端点。读写头回到带子的左端点。 3) 消去一个消去一个 a，并向右扫描直到，并向右扫描直到 b 出现。在出现。在 b 与与 c 之间来回之间来回移动，成对地消去移动，成对地消去 b 和和 c，直到把所有的，直到把所有的 b 都消去。如都消去。如果果 c 全消除后还有
25、全消除后还有 b，则拒绝。，则拒绝。 4) 如果还有如果还有 a 未消去，则恢复所有已消去的未消去，则恢复所有已消去的 b，再重复第，再重复第 3步。如果所有的步。如果所有的 a 都已被消去，则检查所有的都已被消去，则检查所有的 c 是否都是否都已被消去。如果是，则接受，否则拒绝。已被消去。如果是，则接受，否则拒绝。”33图灵机举例例例3.7 图灵机图灵机 M4 解所谓的元素区分问题。给出一列解所谓的元素区分问题。给出一列 0, 1 组组成的字符串系列，字符串之间用符号成的字符串系列，字符串之间用符号 # 隔开，隔开，M4 的任务的任务是：如果此序列中的所有字符串都不同，则接受。是：如果此序列
26、中的所有字符串都不同，则接受。此语言是：此语言是：E= #x1 #x2 #xl，xi 0,1*, 且对任意且对任意 i j， xi xj 机器机器 M4 将将 x1 与与 x2 到到 xl 进行比较，然后将进行比较，然后将 x2 与与 x3 到到 xl 进行比进行比较，依此类推。较，依此类推。M4 的非形式描述如下。的非形式描述如下。34图灵机举例M4=“对于输入的对于输入的 w： 1) 在最左端的带符号的顶上做个记号。如果此带符号是空白在最左端的带符号的顶上做个记号。如果此带符号是空白符，则接受。如果此符号是符，则接受。如果此符号是 #，则进行下一步。否则，拒，则进行下一步。否则，拒绝。绝。
27、 2) 向右扫描下一个向右扫描下一个 #，并在其顶上做第二个记号。如果在遇，并在其顶上做第二个记号。如果在遇到空白符之前没有遇到到空白符之前没有遇到 #，则带上只有，则带上只有 x1 ，因此接受。，因此接受。 3) 通过来回移动，比较做了记号的通过来回移动，比较做了记号的 # 的右边的两个字符串，的右边的两个字符串，如果它们相等，则拒绝。如果它们相等，则拒绝。 4) 将两个记号中右边的那个向右移到下一个将两个记号中右边的那个向右移到下一个 # 上。如果在碰上。如果在碰到空白符之前没有遇到到空白符之前没有遇到 #，则将左边的记号向右移到下一，则将左边的记号向右移到下一个个 # 上，并且将右边记号
28、移到后面的上，并且将右边记号移到后面的 # 上。如果这时右上。如果这时右边记号还找不到边记号还找不到 #，则所有的字符串都已经比较过了，因，则所有的字符串都已经比较过了，因而接受。而接受。 5) 转到第转到第 3 步继续执行。步继续执行。”35主要内容主要内容3.1 丘奇丘奇图灵论题图灵论题3.1.1 图灵机的形式化定义图灵机的形式化定义3.1.2 图灵机的例子图灵机的例子3.2 图灵机的变形图灵机的变形3.2.1 多带图灵机多带图灵机3.2.2 非确定型图灵机非确定型图灵机3.2.3 枚举器枚举器3.2.4 与其他模型的等价性与其他模型的等价性3.3 算法的定义算法的定义3.3.1 希尔伯特
29、问题希尔伯特问题3.3.2 描述图灵机的术语描述图灵机的术语36图灵机的变形图灵机的变形q从不同的方面对从不同的方面对 TM 进行扩充。进行扩充。双向无穷带双向无穷带 TM 允许允许 TM 的的输入带是无穷的输入带是无穷的。多带多带 TM 允许允许 TM 有有多于一条的输入带多于一条的输入带。此时每条带上将有一个读。此时每条带上将有一个读头。头。不确定的不确定的 TM 允许允许 TM 在某一状态下根据读入的符号在某一状态下根据读入的符号选择地进行某选择地进行某一个动作一个动作：进入某个状态，在读头的当前位置印刷某个符号，将读：进入某个状态，在读头的当前位置印刷某个符号，将读头移向某个方向。头移
30、向某个方向。多维多维 TM 相当于在双向相当于在双向 TM 的基础上进一步扩充，允许的基础上进一步扩充，允许TM 的的“输输入带入带”向更多的方向延伸向更多的方向延伸。枚举器枚举器允许图灵机允许图灵机带有打印机带有打印机。q它们与基本的它们与基本的 TM 等价。等价。q在形式变化中在形式变化中保持不变的性质保持不变的性质称为称为稳健性稳健性。37多带图灵机q多带图灵机多带图灵机 (multitape Turing Machine) 很像普通图灵机，很像普通图灵机，只是有多个带子，只是有多个带子，每个带子都有自己的读写头每个带子都有自己的读写头，用于读和写。，用于读和写。开始时，输入出现在第一个
31、带子上，其它的带子都是空白开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许多个带子同时进行读、写和移动读写头，转移函数改为允许多个带子同时进行读、写和移动读写头，其形式为：其形式为： ： Q k Q kL, R, Sk 此处此处 k 是带子的个数。表达式是带子的个数。表达式 ( qi , a1 , a2 , , ak ) = ( qj, b1, b2, , bk , L, R, , L) 指的是：若机器处于状态指的是：若机器处于状态 qi ，读写头，读写头 1 到到 k 所读的符号分别所读的符号分别是是 a1 到到 ak ，则机器转移到状态则机器转移到状态 qj，各读写头分
32、别，各读写头分别写下符号写下符号 b1 到到 bk，且按此式所指示的那样移动每个读写头。，且按此式所指示的那样移动每个读写头。38多带图灵机定理定理定理定理3.83.8每个多带图灵机等价于某一个单带图灵机每个多带图灵机等价于某一个单带图灵机将一将一 个多带个多带 TM M 转换为一个与之等价的单带转换为一个与之等价的单带 TM S，关健是，关健是怎样用怎样用 S 来模拟来模拟 M。假设假设 M 有有 k 个带子。个带子。 S 把此把此 k 个带子的信息都存储在它的唯个带子的信息都存储在它的唯一带子上，并以此来模拟一带子上，并以此来模拟 k 个带子的效果，它用一个新的符号个带子的效果，它用一个新
33、的符号 # 作为定界符，以分开不同带子的内容。除了带内容之外，作为定界符，以分开不同带子的内容。除了带内容之外，S 还必须记录读写头的位置。为此，它在一个符号的顶上加个点，还必须记录读写头的位置。为此，它在一个符号的顶上加个点，以此来标记读写头在其带上的位置。以此来标记读写头在其带上的位置。S 把它们想象为虚拟带子把它们想象为虚拟带子和虚拟读写头。像以前一样，加点的带符号应是已经加进带字和虚拟读写头。像以前一样，加点的带符号应是已经加进带字母表的新符号。母表的新符号。39多带图灵机01010Maaaba#01010#aaa#ba#S40多带图灵机qS = “对于输入对于输入 w=w1 wn：
34、1) S 在白己的带子上放入在白己的带子上放入 #w1w2wn# # # #（上边没（上边没加点）加点） 此格式表示了此格式表示了 M 的全部的全部 k 个带子的内容。个带子的内容。 2)为了模拟多带机的一步移动，为了模拟多带机的一步移动， S在其带子上从标记左端点在其带子上从标记左端点的第一个的第一个 # 开始扫描，一直扫描到标记右端点的第开始扫描，一直扫描到标记右端点的第 (k+1) 个个 #。其目的是确定虚拟读写头下的符号。然后。其目的是确定虚拟读写头下的符号。然后 S 进行第进行第二次扫描，并根据二次扫描，并根据 M 的转移函数指示的运行方式更新其带的转移函数指示的运行方式更新其带子。
35、子。 3)任何时候，只要任何时候，只要 S 将某个虚拟读写头向右移动到某个将某个虚拟读写头向右移动到某个#上上面，就意味着面，就意味着 M 已将自己相应的读写头移动到了其所在的已将自己相应的读写头移动到了其所在的带子中的空白区域上，即以前没有读过的区域上。因此，带子中的空白区域上，即以前没有读过的区域上。因此，S在这个带方格上写下空白符，并将这个带方格到最右端的在这个带方格上写下空白符，并将这个带方格到最右端的带方格中的内容都向右移动一个格。然后再像以前一样继带方格中的内容都向右移动一个格。然后再像以前一样继续模拟。续模拟。” 41多带图灵机推论推论推论推论3.93.9一个语言是图灵可识别的，
36、当且仅当存在多带图一个语言是图灵可识别的，当且仅当存在多带图灵机识别它。灵机识别它。一个图灵可识别语言可由一个普通的一个图灵可识别语言可由一个普通的( (单带单带) )图灵机识别，这图灵机识别，这个普通图灵机是多带图灵机的一个特例，这就证明了此推论个普通图灵机是多带图灵机的一个特例，这就证明了此推论的一个方向。另一个方向可由定理的一个方向。另一个方向可由定理3.8得证。得证。42非确定型图灵机q非确定型图灵机的有如其名，在计算的过程中，机器可以在非确定型图灵机的有如其名，在计算的过程中，机器可以在多种可能性动作中选择一种继续进行。它的转移函数具有如多种可能性动作中选择一种继续进行。它的转移函数
37、具有如下形式：下形式： : Q P(Q L, R） 其计算是一棵树，不同分其计算是一棵树，不同分支支对应着机器的不同可能性。对应着机器的不同可能性。43非确定型图灵机定理定理定理定理3.103.10每个非确定型图灵机都等价于某一个确定型图灵每个非确定型图灵机都等价于某一个确定型图灵机。机。q能用确定型能用确定型 TM D 来模拟非确定型来模拟非确定型 TM N 的计算的证明思的计算的证明思路是：路是：让让 D 试验试验 N 的非确定性计算的所有可能分支，若的非确定性计算的所有可能分支，若 D能在某个分支中到达接受状态，则接受；否则能在某个分支中到达接受状态，则接受；否则 D 的模拟将的模拟将永
38、不终止。永不终止。q将将 N 在输入在输入 w 的计算看作一棵树，树的每个分支代表非确的计算看作一棵树，树的每个分支代表非确定型的分支，结点是定型的分支，结点是N的一个格局，根是起始格局。的一个格局，根是起始格局。TM D在这个树上搜索接受格局。我们采用在这个树上搜索接受格局。我们采用“宽度优先宽度优先”策略搜策略搜索整棵树，这个策略是：索整棵树，这个策略是：在搜索一个深度内的所有分支之在搜索一个深度内的所有分支之后，再去搜索下一个深度内的所有分支后，再去搜索下一个深度内的所有分支。此方法能保证。此方法能保证 D可以访问树的所有结点，直到它遇到接受格局。可以访问树的所有结点，直到它遇到接受格局
39、。44非确定型图灵机q用于模拟的确定型用于模拟的确定型 TM D 有有 3 个带子。根据定理个带子。根据定理 3.8，这等，这等价于只有一个带子。机器价于只有一个带子。机器 D 将这三个带子用于专门用途。将这三个带子用于专门用途。第一个带子包含输入串，且不再改变；第二个带子存放第一个带子包含输入串，且不再改变；第二个带子存放N的带子中的内容，此内容对应的带子中的内容，此内容对应N的非确定性计算的某个分的非确定性计算的某个分支；第三个带子记录支；第三个带子记录 D 在在 N 的非确定性计算树中的位置。的非确定性计算树中的位置。0010Dxx#01x12332312113输入带模拟带地址带45非确
40、定型图灵机q首先考虑第三个带子上表示的数据。首先考虑第三个带子上表示的数据。N N的每个格局确定一个集合，它是的每个格局确定一个集合，它是由此格局可能转移到的下一个格局组成，这些下一个格局是由由此格局可能转移到的下一个格局组成，这些下一个格局是由N N的转移的转移函数指定的。函数指定的。N N的非确定性计算中的每个结点最多有的非确定性计算中的每个结点最多有b b个子结点，其中：个子结点，其中：b b是上述集合中最大的集合所含的元素个数。对树的每个结点，可以给是上述集合中最大的集合所含的元素个数。对树的每个结点，可以给其分配一个地址，它是字母表其分配一个地址，它是字母表 b b= =11，2 2
41、，b b 上的一个串。上的一个串。q例如，把地址例如，把地址231231分配给按以下方式到达的结点：从根出发走到它的第分配给按以下方式到达的结点：从根出发走到它的第二个子结点，再由此走到第三个子结点，最后由此走到第一个子结点。二个子结点，再由此走到第三个子结点，最后由此走到第一个子结点。此串中的数字告诉我们：在模拟此串中的数字告诉我们：在模拟N N的非确定计算的一个分支时下一步应的非确定计算的一个分支时下一步应做什么。如果一个格局所能有的选择太少，则一个符号可能不对应任做什么。如果一个格局所能有的选择太少，则一个符号可能不对应任何选择。此种倩况下，地址将无效，不对应任何结点。第三个带子上何选择
42、。此种倩况下，地址将无效，不对应任何结点。第三个带子上包含包含 b b上的一个串，它代表上的一个串，它代表N N的计算树中如下分支：起点是根，终点是的计算树中如下分支：起点是根，终点是此串表示的地址所对应的结点，除非这个地址是无效的。空串是树根此串表示的地址所对应的结点，除非这个地址是无效的。空串是树根的地址的地址。46非确定型图灵机qD的描述如下：的描述如下：1)开始时，第一个带子包含输入开始时，第一个带子包含输入w，第二和第三个带子都，第二和第三个带子都是空的。是空的。2)把第一个带子复制到第二个带子上。把第一个带子复制到第二个带子上。3)用第二个带子去模拟用第二个带子去模拟N在输入在输入
43、w上的非确定性计算的某个上的非确定性计算的某个分支。在分支。在N的每一步动作之前，查询第三个带子上的下的每一步动作之前，查询第三个带子上的下一个数字，以决定在一个数字，以决定在N的转移函数所允许的选择中作何的转移函数所允许的选择中作何选择。如果第三个带子上没有符号剩下，或这个非确定选择。如果第三个带子上没有符号剩下，或这个非确定性的选择是无效的，则放弃这个分支，转到第性的选择是无效的，则放弃这个分支，转到第4步。如步。如果遇到拒绝格局也转到第果遇到拒绝格局也转到第4步。如果遇到接受格局，则步。如果遇到接受格局，则接受这个输入。接受这个输入。4)在第二个带子上，用字典顺序下的下一个串来替代原有在
44、第二个带子上，用字典顺序下的下一个串来替代原有的串。转到第的串。转到第2步，以模拟步，以模拟N的计算的下一个分支。的计算的下一个分支。47非确定型图灵机推论推论推论推论3.113.11 一个语言是图灵可识别的，当且仅当存在非确一个语言是图灵可识别的，当且仅当存在非确定型图灵机识别它。定型图灵机识别它。推论推论推论推论3.123.12 一个语言是可判定的，当且仅当存在非确定型一个语言是可判定的，当且仅当存在非确定型图灵机判定它。图灵机判定它。确定型图灵机自然是一个非确定型图灵机，此定理的一个方向由此立刻确定型图灵机自然是一个非确定型图灵机，此定理的一个方向由此立刻得证。另个方向可内定理得证。另个
45、方向可内定理3.10得证。得证。48枚举器q它是图灵机的一种变形。粗略地说，它是图灵机的一种变形。粗略地说，枚举器是带有打印机枚举器是带有打印机的图灵机的图灵机，图灵机把打印机当作输出设备，从而可以打印，图灵机把打印机当作输出设备，从而可以打印串。每当图灵机想在打印序列中增加一个串时，就把此串串。每当图灵机想在打印序列中增加一个串时，就把此串送到打印机。送到打印机。q枚举器以空白输入带开始运行，枚举器以空白输入带开始运行，如果不停机，它可能会打如果不停机，它可能会打印出串的一个无限序列。枚举器印出串的一个无限序列。枚举器 E 所枚举的语言是最终打所枚举的语言是最终打印出的串的集合印出的串的集合
46、。而且。而且 E 可能以任意顺序生成这个语言中可能以任意顺序生成这个语言中的串，甚至还会有重复。的串，甚至还会有重复。49枚举器示意图控制器控制器打印机打印机aababaabba0100工作带工作带50枚举器定理定理定理定理3.133.13 一个语言是图灵可识别的，当且仅当存在枚举器一个语言是图灵可识别的，当且仅当存在枚举器枚举它。枚举它。51枚举器q首先证明，如果有枚举器首先证明，如果有枚举器 E 枚举语言枚举语言 A，则有，则有 TM M 识别识别 A。 TM M如下运行：如下运行： M=“对于输入对于输入w： 1)运行运行E。每当。每当E输出一个串时，将之与输出一个串时，将之与w比较。比
47、较。 2)如果如果w曾经在曾经在E的输出中出现过，则接受。的输出中出现过，则接受。” 显然，显然，M接受在接受在E的输出序列中出现过的那些串。的输出序列中出现过的那些串。q现在证明另一个方向。设现在证明另一个方向。设s1， s2， s3，是是 *中的所有串。如果有中的所有串。如果有TM M识别语言识别语言A，为为A构造枚举器构造枚举器E如下：如下： E“忽略输入。忽略输入。 1)对对i1，2，3，重复下列步骤。，重复下列步骤。 2)对对s1， s2， s3， ，si中的每一个，中的每一个，M以其作为输入运行以其作为输入运行i步步 3)如果有计算接受，则打印出相应的如果有计算接受，则打印出相应的
48、sj 。” 如果如果M接受串接受串s，它终将出现在，它终将出现在E生成的打印列表中。生成的打印列表中。52通用图灵机q通用通用 TM (universal Turing machine) 实现对所有实现对所有 TM 的模拟。的模拟。q编码系统编码系统它可以在实现对它可以在实现对 TM 的表示的同时，实现对该的表示的同时，实现对该 TM 处理的句子的表处理的句子的表示。示。用用 0 和和 1 对这些除空白符以外的其他的带符号进行编码。同时也可对这些除空白符以外的其他的带符号进行编码。同时也可以用以用 0 和和 1 对对 TM 的移动函数进行编码。的移动函数进行编码。 53通用图灵机qM = (q
49、1, q2, , qn, 0,1, 0,1,B, ,q1 , B , q2) q用用X1, X2, X3分别表示分别表示 0,1,B，用用D1 , D2分别表示分别表示 R,L。 (qi, Xj)=(qk , Xl, Dm) 可以用可以用0i10j10k10l10m表示。表示。qM 可用可用 111 code1 11 code2 11 11 coder 111 qcodet 是动作是动作(qi, Xj)=(qk , Xl, Dm)的形如的形如0i10j10k10l10m的的编码。编码。 qTM M 和它的输入串和它的输入串 w 则可以表示成则可以表示成 111 code1 11 code2 1
50、1 11 coder 111w q按照规范顺序分别对表示按照规范顺序分别对表示 TM 的符号行和表示输入的符号的符号行和表示输入的符号行进行排序。行进行排序。54通用图灵机q设设TM M2=( q1, q2, q3, q4, 0, 1, 0, 1, B, , q4 , B ,q3)，其中，其中的的定义如下定义如下:(q4, 0) = (q4, 0, R)(q4, 1) = (q1, 1, R)(q1, 0) = (q1, 0, R)(q1, 1) = (q2, 1, R)(q2, 0) = (q2, 0, R)(q2, 1) = (q3, 1, R) q编码为编码为11100001010000
51、10101100001001010010110101010101101001001001011001010010101100100100010010111q通用通用 TM 检查检查 M 是否接受字符串是否接受字符串 001101110 1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111 00110111055主要内容主要内容3.1 丘奇丘奇图灵论题图灵论题3.1.1 图灵机的形式化定义图灵机的形式化定义3.1.2 图灵机的例子图灵机的例子3.2 图灵机的变形图灵机
52、的变形3.2.1 多带图灵机多带图灵机3.2.2 非确定型图灵机非确定型图灵机3.2.3 枚举器枚举器3.2.4 与其他模型的等价性与其他模型的等价性3.3 算法的定义算法的定义3.3.1 希尔伯特问题希尔伯特问题3.3.2 描述图灵机的术语描述图灵机的术语56算法的定义q非形式地说，非形式地说，算法算法是为实现某个任务而构造的简单指令集。是为实现某个任务而构造的简单指令集。在日常用语来说，算法有时称为过程或处方。算法在数学在日常用语来说，算法有时称为过程或处方。算法在数学中也起着重要的作用。古代数学文献中包含了各种各样任中也起着重要的作用。古代数学文献中包含了各种各样任务的算法描述，如寻找素
53、数和最大公因子。当代数学中更务的算法描述，如寻找素数和最大公因子。当代数学中更是充满了算法。是充满了算法。57希尔伯特问题q1900年希尔伯特提出了年希尔伯特提出了23个数学问题。其中的第个数学问题。其中的第10个问题个问题是关于算法的。是关于算法的。通过有限多次运算就可以决定的过程。通过有限多次运算就可以决定的过程。q一个一个多项式多项式是一些项的和，其中：每个项都是一个常数和是一些项的和，其中：每个项都是一个常数和一些变元的积，此常数叫一些变元的积，此常数叫系数系数（coefficient）。）。q例如，例如，6xxxyzz=6x3yz2是一个项，其系数是是一个项，其系数是6； 6x3yz
54、2+3xy2-x3-10 是一个多项式，它有四个项和三个变元是一个多项式，它有四个项和三个变元x、y、zq多项式的多项式的根根（root）是对它的变元的一个赋值，使此多项式）是对它的变元的一个赋值，使此多项式的值为的值为0。q上述多项式的一个根是上述多项式的一个根是x=5、y=3和和z=0，这个根是，这个根是整数根整数根（integral root），因为所有变元都被赋予整数值。），因为所有变元都被赋予整数值。58希尔伯特问题q丘奇丘奇-图灵论题（图灵论题（Church-Turing thesis）q希尔伯特第希尔伯特第10问题旨在设计一个算法来检测一个多项式是问题旨在设计一个算法来检测一个多
55、项式是否有整数根。否有整数根。q 现在用上述术语来重新陈述希尔伯特第现在用上述术语来重新陈述希尔伯特第10问题，设问题，设 D= p | p 是有整数根的多项式是有整数根的多项式 本质上，希尔伯特第本质上，希尔伯特第 10 个问题是问；个问题是问；集合集合 D 是不是可判定是不是可判定的的? 答案是否定的。答案是否定的。 算法的直觉概念算法的直觉概念 等于等于 图灵机算法图灵机算法59希尔伯特问题q考虑只有一个变元的多项式，如考虑只有一个变元的多项式，如4x3-2x2+x-7。设。设 D1 = p | p 是有整数根是有整数根x的多项式的多项式q下面是识别下面是识别 D1 的图灵机的图灵机 M
56、1： M1 =“输入是关于变元输入是关于变元 x 的一个多项式的一个多项式 p 当当 x 相继被设置为值相继被设置为值0, 1, -1, 2, -2, 3, -1, 时，求时，求 p 的值，的值，一旦求得一旦求得 0 值，就接受。值，就接受。” 如果如果 p 有整数根，有整数根，M1 最终将找到它，从而接受；最终将找到它，从而接受；如果如果 p 没有整数根，则没有整数根，则 M1 将永远运行下去。将永远运行下去。q对于多变元的情形，可以设计一个类似的图灵机对于多变元的情形，可以设计一个类似的图灵机 M 来识别来识别D，只是，只是 M 要检查多个变元所有可能取的整数值。要检查多个变元所有可能取的
57、整数值。60描述图灵机的术语q描述的详细程度有三种：描述的详细程度有三种： 形式化描述形式化描述 实现描述实现描述 高水平描述高水平描述61图灵机的格式和记号q图灵机的输入总是一个串。如果想以一个对象而不是字符图灵机的输入总是一个串。如果想以一个对象而不是字符串的作为输入，必须先将那个对象字符串化。串的作为输入，必须先将那个对象字符串化。q对象对象 O 的编码成字符串的记号是的编码成字符串的记号是 。如果有多个对象。如果有多个对象O1, O2, Ok，它们的编码是一个串，记为，它们的编码是一个串，记为。q描述图灵机算法的格式是带引号的文字段，且描述图灵机算法的格式是带引号的文字段，且排成锯齿形
58、排成锯齿形状状。将算法分成几个步骤，每个步骤可能包括图灵机计算。将算法分成几个步骤，每个步骤可能包括图灵机计算的许多步，用更深的缩进方式来指示算法的分块结构。的许多步，用更深的缩进方式来指示算法的分块结构。算算法的第一行描述机器的输入法的第一行描述机器的输入。如果输入描述仅仅被写成。如果输入描述仅仅被写成w，则这个串就被当作输入，如果输入描述是一个对象的编码则这个串就被当作输入，如果输入描述是一个对象的编码 ，则暗示图灵机需要首先检查此输入是否确实是所要，则暗示图灵机需要首先检查此输入是否确实是所要的对象的编码，如果不是，则拒绝它。的对象的编码，如果不是，则拒绝它。62描述图灵机的术语例例3.
59、14 设设 A 是由表示连通无向图的串构成的语言。回忆一下，是由表示连通无向图的串构成的语言。回忆一下，如果一个图从任意顶点出发，都可以沿着边走到其它如果一个图从任意顶点出发，都可以沿着边走到其它所有顶点，则称这个图是所有顶点，则称这个图是连通的连通的。记。记 A 为为A = | G 是连通无向图是连通无向图 下面是判定下面是判定 A 的的 TM M 的一个高层次描述：的一个高层次描述：M=“输入是图输入是图 G 的编码的编码 ： 1)选择选择 G 的第一个顶点，并标记之。的第一个顶点，并标记之。 2)重复下列步骤，直到没有新的顶点可作标记。重复下列步骤，直到没有新的顶点可作标记。 3)对于对
60、于 G 的每一个顶点，如果能通过一条边将其连到另一的每一个顶点，如果能通过一条边将其连到另一 个已被标记的顶点，则标记该顶点。个已被标记的顶点，则标记该顶点。 4)扫描扫描 G 的所有顶点，确定它们是否都已做了标记，如果的所有顶点，确定它们是否都已做了标记，如果 是，则接受，否则拒绝。是，则接受，否则拒绝。63描述图灵机的术语1234G=(1,2,3,4,)(1,2),(2,3),(3,1),(1,4)64本章小结本章小结q丘奇丘奇图灵论题图灵论题图灵机的形式化定义、构造方法图灵机的形式化定义、构造方法q图灵机的变形图灵机的变形多带图灵机、多带图灵机、 非确定型图灵机、枚举器、通用图灵机非确定型图灵机、枚举器、通用图灵机q算法的定义算法的定义熟悉算法的描述方式、描述图灵机的术语熟悉算法的描述方式、描述图灵机的术语65作业q3.1, 3.2, 3.4, 3.5, 3.7, 3.15, 3.1666
