算法图灵机及可计算性理论.pptVIP

图灵机（Turing Machine) 图灵机（Turing Machine) TM运行由 确定:当前状态为q，所读字符为s ，读写头不变， ， ，读写头左移一格，s不变， ，读写头右移一格，s不变， 无定义，则停机 Church-Turing论题：凡是可计算的过程都可用图灵机实现 * 图灵机与可计算性理论 图灵对计算本质的揭示 在哥德尔研究成果的影响下20世纪30年代后期，图灵﹙A．M．Turing﹚从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识。 根据图灵的研究，直观地说，所谓计算就是计算者﹙人或机器﹚对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。图灵用形式化方法成功表述可计算这一过程的本质。 有限状态控制器 1 1 1 1 1 1 0 0 0 0 0 0 0 B B B 1 …… …… 读写头 当图灵机的读写头扫描到一个格的字符时，根据控制器的当前状态和扫描到的字符，决定图灵机的动作。包括3方面： (1) 控制器进行状态转换（决定下一状态）； (2) 读写头在当前格写上新的字符； (3) 决定读写头向左或向右移动一格。 其他图灵机模型 “实际的”的图灵机模型 单带图灵机（1TM） 多带图灵机（kTM） 随机存取机（RAM） “实际的” 单位时间内完成的工作量有一个多项式上界 所有“实际的”计算模型多项式时间等价 其他图灵机模型 凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。 从理论上，从根本上说，一个算法就是一个确定的、对任意输入都停机的图灵机。 可计算函数与可计算语言的定义同图灵机的停机问题有密切的关系。 设L为一个语言，若被一个图灵机M接受，则称L为一个递归可枚举语言；若L被一个图灵机M接受，且对任意输入串，M都停机，则称L为一个递归语言。 设 为一个整函数，若存在图灵机M实现f的计算功能（其中，对某些输入M可能不停机），则称f为一个部分递归函数；若存在图灵机M实现f的计算功能，且对于f任意一组输入 ，M都能停机，称f为一个完全递归函数。 一个函数（语言）是可计算函数（语言）当且仅当它是一个完全递归函数（递归语言）。一个函数（语言）是部分可计算的当且仅当它是一个部分递归函数（递归可枚举语言）。 对于可计算函数，可以设计算法进行计算。对于每一个输入，算法都能终止，并输出计算结果。 多带图灵机 确定的图灵机是现代电子计算机的理论模型。一个对任意输入都停机的确定图灵机在多项式时间内可解的问题，必然存在多项式时间复杂度的计算机求解算法。 不确定的图灵机只是一种理论上的计算模型。 不确定图灵机可解的问题，虽然也可以用确定的图灵机求解，但时间上的耗费（或说求解步数）是不一样的。 用不确定的图灵机以多项式时间界可求解的问题，用确定的图灵机不能保证在多项式时间界内可求解，但用确定的图灵机以指数时间界是肯定可以求解的。 用确定的图灵机以多项式时间界可解的问题称为P类问题；用不确定的图灵机以多项式时间界可解的问题称为NP类问题。 确定的图灵机可以看作不确定的图灵机的一种特殊情形，因此这两个问题集合之间存在子集关系，即 。 现在的问题是：P是NP的真子集吗？ 换个提法：是否如果，即用不确定的图灵机以多项式时间界可求解的问题，也都存在多项式时间界的确定的图灵机求解算法， 这就意味着可以用现代电子计算机在多项式时间界内求解。 这个问题引起了许多计算科学家和计算机科学家的极大兴趣，因为大量有实际应用背景的问题（其中许多都可以归结为图论或最优化理论问题）都可以在多项式时间界内用不确定图灵机求解（而又未找到多项式时间复杂性的计算机算法）。 另一方面，自这个问题提出已经经历40多年，虽然许多专家和学者做了大量的工作，却一直未能得到肯定或否定的结果。 美国的 Ｃｌａｙ 数学研究所于2000年5月24日在巴黎法兰西学院宣布设立100万美元奖金，征解“NP=P?”问题，而且把这个问列位该研究所悬赏征解的七个问题之首。 NP=P? 计算机科学王冠上的明珠 由我国118位科学家（其中有25位中国科学院院士）合作编写的《21世纪100个科学难题》（吉林人民出版社，1998年6月出版）一书也把这个问题列入其中。 “千僖难题”之一：P（多项式算法）问题对