《计算复杂性课件.ppt》由会员分享，可在线阅读，更多相关《计算复杂性课件.ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、可计算性与计算复杂性李占山李占山1000个图片的拼图，如果没有考虑把握技巧，那么对于每个图片有正反面、左右和对错3种组合8种状态，这样我们把所有图片拼在一起需要考虑81000种状态（步骤）情况拼图，这是一个惊人的数字，用计算机求解在我们的有生之年是看不到结果的。难道这个问题就没有结果了吗？非也，我们人不是在玩这种游戏吗？我只用了一两天甚至更短的时间就成功了，哪有你老师说的那么复杂？那样不是很郁闷吗？我拼图成功很是快乐，为什么？拼图游戏拼图游戏从拼图游戏到解现实生活中从拼图游戏到解现实生活中的实际问题的解决的实际问题的解决-同学，游戏不是这样玩的！我们的课程可以使你从可郁闷性与郁闷复我们的课程可
2、以使你从可郁闷性与郁闷复杂性到可快乐性与快乐复杂性的。怎么办杂性到可快乐性与快乐复杂性的。怎么办？分类分解问题呗！首先把图片都翻到相？分类分解问题呗！首先把图片都翻到相同一面，最坏时要做同一面，最坏时要做10001000次，如果图片字次，如果图片字母标号有母标号有2020种，然后把它们根据字母标号种，然后把它们根据字母标号分成分成2020子类，每一子类再根据字母正反分子类，每一子类再根据字母正反分为为2 2个子子类，同样拼图时相邻的图片是交个子子类，同样拼图时相邻的图片是交错排列的，按照这样的分类方法进行拼图错排列的，按照这样的分类方法进行拼图看看最坏时我们需要多少个步骤？看看最坏时我们需要多
3、少个步骤？玩游戏是一门学问呦！1000+1000+20 250个状态（步骤），这些个状态（步骤），这些状态步骤完全在你的有限时间掌控之中，状态步骤完全在你的有限时间掌控之中，因此能够在一两天甚至更短时间内完成拼因此能够在一两天甚至更短时间内完成拼图任务。嗷！原来是这样的呀！看来学好图任务。嗷！原来是这样的呀！看来学好这门课会使我们从这门课会使我们从可郁闷性与郁闷复杂性可郁闷性与郁闷复杂性到可快乐性与快乐复杂性的！为了学到可快乐性与快乐复杂性的！为了学好这门课程我们有必要介绍这门课程的本好这门课程我们有必要介绍这门课程的本质与定位以及一些重要历史人物，他们是质与定位以及一些重要历史人物，他们是？
4、计算学科（计算学科（Computing Science）即我即我们所熟悉的计算机科学与技术们所熟悉的计算机科学与技术(Computer Science and Technology)。计算学科是对计算学科是对描述和变换信息的算法过程，包括其理论、描述和变换信息的算法过程，包括其理论、分析、设计、效率分析、实现和应用等进行分析、设计、效率分析、实现和应用等进行的系统研究的一门学科。它涉及计算过程的的系统研究的一门学科。它涉及计算过程的分析如分析如可计算性、算法，研究有关计算机的可计算性、算法，研究有关计算机的各种现象各种现象、揭示其规律与本质如计算机的设、揭示其规律与本质如计算机的设计和使用、可
5、计算性硬件和软件的实际实现计和使用、可计算性硬件和软件的实际实现问题。问题。计算学科的基本问题是能行与效率的计算学科的基本问题是能行与效率的问题问题,即它的核心问题是即它的核心问题是“能行能行”问题问题(Practicability)：1)什么是（实际）可计算的？什么是什么是（实际）可计算的？什么是（实际）不可计算的？（实际）不可计算的？2)如何保证计算的自动性、有效性及如何保证计算的自动性、有效性及正确性？正确性？1985年春，年春，ACM（美国计算机协会）和美国计算机协会）和IEEECS（国际电子电气工程师学会计算机分会）组成国际电子电气工程师学会计算机分会）组成联合攻关小组，开始了对联合
6、攻关小组，开始了对“计算作为一门学科计算作为一门学科”的的存在性证明。存在性证明。1989年年1月，该小组提交了计算作月，该小组提交了计算作为一门学科（为一门学科（Computing as a discipline）的报的报告。第一次给出了计算学科一个透彻的定义，回答告。第一次给出了计算学科一个透彻的定义，回答了计算学科中长期以来一直争论的一些问题，完成了计算学科中长期以来一直争论的一些问题，完成了计算学科的了计算学科的“存在性存在性”证明，还提出了未来计算证明，还提出了未来计算科学教育必须解决的二个重大问题科学教育必须解决的二个重大问题整个学科核整个学科核心课程详细设计及整个学科综述性导引课
7、程的构建。心课程详细设计及整个学科综述性导引课程的构建。1991年，在这报告的基础上提交了关于计算学科年，在这报告的基础上提交了关于计算学科教学计划教学计划CC1991（Computing Curricula 1991）。）。2001年年12月，提交了最终的月，提交了最终的CC2001报告。报告。计算作为一门学科报告及计算作为一门学科报告及CC1991、CC2001一起解决了三个重要问题：一起解决了三个重要问题：第一个重大问题（第一个重大问题（计算作为一门计算作为一门学科的存在性证明学科的存在性证明）的解决。对学科本身的）的解决。对学科本身的发展至关重要。如果在众多分支领域都取得发展至关重要。
8、如果在众多分支领域都取得了重大成果并已得到广泛应用的了重大成果并已得到广泛应用的“计算计算”，连作为一门学科的地位都不清楚，那么它的连作为一门学科的地位都不清楚，那么它的发展势必要受到很大的限制。发展势必要受到很大的限制。第二个重大问题（第二个重大问题（整个学科核心课程详整个学科核心课程详细设计细设计）的解决，将为高校制定计算机教学）的解决，将为高校制定计算机教学计划奠定基础。确定一个公认的本科生应该计划奠定基础。确定一个公认的本科生应该掌握的核心内容，将避免教学计划设计中的掌握的核心内容，将避免教学计划设计中的随意性，从而为我们科学地制定教学计划奠随意性，从而为我们科学地制定教学计划奠定基础
9、。定基础。第三个重大问题（第三个重大问题（整个学科综述性导引整个学科综述性导引课程的构建课程的构建）的解决，将使人们对整个学科）的解决，将使人们对整个学科的认知科学化、系统化和逻辑化。如果人们的认知科学化、系统化和逻辑化。如果人们对计算学科的认知能建立在公理化的基础之对计算学科的认知能建立在公理化的基础之上，则该学科可被认为是严谨的科学、成熟上，则该学科可被认为是严谨的科学、成熟的学科，从而有助于它的发展，并将由此而的学科，从而有助于它的发展，并将由此而得到人们的尊重。得到人们的尊重。攻关小组的结论是：计算学科所攻关小组的结论是：计算学科所研究的根本问题是研究的根本问题是能行问题能行问题（什么
10、能被（什么能被（有效地）自动进行）。计算学科的基（有效地）自动进行）。计算学科的基本原理已纳入理论、抽象和设计这本原理已纳入理论、抽象和设计这3个个具有科学技术方法意义的过程中。学科具有科学技术方法意义的过程中。学科的各分支领域正是通过这的各分支领域正是通过这3个过程来实个过程来实现它们各自的目标。而这现它们各自的目标。而这3个过程要解个过程要解决的都是计算过程中的决的都是计算过程中的“能行性能行性”和和“有效性有效性”问题。问题。与数学相比，电子技术的重要性对计算与数学相比，电子技术的重要性对计算科学而言不如数学，因为数学提供了计算科科学而言不如数学，因为数学提供了计算科学最重要的学科思想和
11、方法论基础，而电子学最重要的学科思想和方法论基础，而电子技术只提供了电子计算机的实现技术，它仅技术只提供了电子计算机的实现技术，它仅仅只是对计算科学许多思想和方法的一种当仅只是对计算科学许多思想和方法的一种当前最现实、最有效的实现技术手段而已。当前最现实、最有效的实现技术手段而已。当科学技术的手段提到发展时，完全有可能有科学技术的手段提到发展时，完全有可能有某一项新技术归结为有效地取代电子技术某一项新技术归结为有效地取代电子技术（如光技术、生物技术等等），但计算科学（如光技术、生物技术等等），但计算科学的数学基础可能变化不大。的数学基础可能变化不大。从事计算科学的人都知道，计算科学中从事计算科
12、学的人都知道，计算科学中不仅许多理论是用数学描述的，而且许多技不仅许多理论是用数学描述的，而且许多技术也是用数学描述的。大多数计算科学理论术也是用数学描述的。大多数计算科学理论不仅仅是对研究对象变化规律的陈述，而且不仅仅是对研究对象变化规律的陈述，而且由于能行性这一本质的核心问题和特点的作由于能行性这一本质的核心问题和特点的作用，理论描述中常通过方法折射出技术的思用，理论描述中常通过方法折射出技术的思想和步骤，而从理论通过方法跨越到技术则想和步骤，而从理论通过方法跨越到技术则完全取决于理论的深刻认识和理解。一个人完全取决于理论的深刻认识和理解。一个人如果看懂了以形式化方法描述的技术文献，如果看
13、懂了以形式化方法描述的技术文献，自然明白技术上应该怎样去做。自然明白技术上应该怎样去做。至于计算机技术专业的学生为何要学习至于计算机技术专业的学生为何要学习数学这个问题的答案，了解了上面所讲的计数学这个问题的答案，了解了上面所讲的计算学科与数学的关系后就不言而喻了：算学科与数学的关系后就不言而喻了：计算计算机科学植根于数学，但又不同于数学，从而机科学植根于数学，但又不同于数学，从而可计算理论的基础知识就需要掌握，因为这可计算理论的基础知识就需要掌握，因为这能够能够提高我们本身的提高我们本身的逻辑推理能力、抽象思逻辑推理能力、抽象思维能力和形式化思维能力维能力和形式化思维能力，从而今后在学习，从
14、而今后在学习任何一门计算机科学的专业主干课程时，都任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。不会遇上任何思维理解上的困难。当前计算机科学在发展过程中面对着如下两个当前计算机科学在发展过程中面对着如下两个问题问题：一是信息革命要求计算机科学要将计算机的一是信息革命要求计算机科学要将计算机的应用扩大到包含所有的问题领域和深入到每个问题应用扩大到包含所有的问题领域和深入到每个问题领域的深处而越来越细致越来越复杂；二是一旦让领域的深处而越来越细致越来越复杂；二是一旦让计算机去解决问题，那么计算机应自动地在有限和计算机去解决问题，那么计算机应自动地在有限和有效的时间内得出解。有
15、效的时间内得出解。前者指出计算机科学的任务前者指出计算机科学的任务就是要用计算机的硬件、外设和软件构成一个系统，就是要用计算机的硬件、外设和软件构成一个系统，使得许多不同领域的问题都能在这样的计算机系统使得许多不同领域的问题都能在这样的计算机系统中得到解决。为了完成这个任务，就必须用一种符中得到解决。为了完成这个任务，就必须用一种符号语言构成一个包括了不同领域的通用模型。号语言构成一个包括了不同领域的通用模型。计算理论就是指出构成一个包括了不同领计算理论就是指出构成一个包括了不同领域的通用模型的思维方法，并且告诉我们怎域的通用模型的思维方法，并且告诉我们怎样用不同的语言（符号语言、图形语言、逻
16、样用不同的语言（符号语言、图形语言、逻辑语言等）从最简单的对象（集合）出发表辑语言等）从最简单的对象（集合）出发表示通用模型。后者指出计算机科学必须了解示通用模型。后者指出计算机科学必须了解让计算机去解决问题在通用模型中的结构，让计算机去解决问题在通用模型中的结构，由于要求在有限和有效时间内计算机自动完由于要求在有限和有效时间内计算机自动完成，那么问题求解的方法必然是构造性的。成，那么问题求解的方法必然是构造性的。(2)从计算机科学学生能力角度培养的看从计算机科学学生能力角度培养的看计算理论的作用计算理论的作用。计算机出现的五十多年间，人们追求计算机出现的五十多年间，人们追求着和出现了许多计算
17、机信息革命带来的信息着和出现了许多计算机信息革命带来的信息产品，但是信息产品受工业产品的观念上的产品，但是信息产品受工业产品的观念上的影响，使得计算机科学的学科发展带来了偏影响，使得计算机科学的学科发展带来了偏差，使得整个学科的发展都是差，使得整个学科的发展都是“软件跟着硬软件跟着硬件走件走”。我们不能将自己的学生培养成计算。我们不能将自己的学生培养成计算机系统的奴隶，而应该培养成计算机系统的机系统的奴隶，而应该培养成计算机系统的主人，我们的学生不能给计算机系统所塑造，主人，我们的学生不能给计算机系统所塑造，将他们变成计算机，而是教育学生怎样地塑将他们变成计算机，而是教育学生怎样地塑造计算机系
18、统。造计算机系统。在计算机科学知识掌握的过程中应是在计算机科学知识掌握的过程中应是“硬硬件跟着软件走，软件跟着模型走，模型跟着件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走学科实际应用走；学科实际应用跟着自然走”。而最主要的培养环节应该是。而最主要的培养环节应该是软件跟着模软件跟着模型走型走，模型跟着学科实际应用走。关于学生，模型跟着学科实际应用走。关于学生的培养目标就是要培养自己的学生能够根据的培养目标就是要培养自己的学生能够根据实际应用问题提出计算机应用的模型，并用实际应用问题提出计算机应用的模型，并用硬件和软件资源去构造计算机系统去完成模硬件和软件资源去构造
19、计算机系统去完成模型中所提出来的工作。型中所提出来的工作。首先，计算机系统要解决的问题并不是个别的问首先，计算机系统要解决的问题并不是个别的问题，也并不是某个领域上的特殊问题，要解决某个题，也并不是某个领域上的特殊问题，要解决某个领域的所有能用计算机进行计算的问题，因此，关领域的所有能用计算机进行计算的问题，因此，关于计算机科学的思维方法必须是在足够通用的层面于计算机科学的思维方法必须是在足够通用的层面上的思维方法。如果所掌握或所习惯的思维方法仅上的思维方法。如果所掌握或所习惯的思维方法仅限制在是某些特殊的领域，那么，随着计算机应用限制在是某些特殊的领域，那么，随着计算机应用的不断扩大和计算机
20、信息革命的不断扩大，将会使的不断扩大和计算机信息革命的不断扩大，将会使得思维的方法带有很大的局限性。当然，最通用的得思维的方法带有很大的局限性。当然，最通用的层面是自然层面，然而，自然层面上的对象还不能层面是自然层面，然而，自然层面上的对象还不能为现代计算机为现代计算机(现代计算模型现代计算模型)所了解。因为，我们所了解。因为，我们选择塑造计算机系统的层面既带有最大的通用性，选择塑造计算机系统的层面既带有最大的通用性，又能为现代计算机系统所了解的层面。在现代计算又能为现代计算机系统所了解的层面。在现代计算技术的支持下，这个层面就是符号处理层面。技术的支持下，这个层面就是符号处理层面。其次，我们
21、是要去塑造计算机系统，我们其次，我们是要去塑造计算机系统，我们的所有思维都要立足于能的所有思维都要立足于能“塑造塑造”性，因此，性，因此，思维的可构造性，即在考虑构成计算机系统思维的可构造性，即在考虑构成计算机系统的所有对象都必须能够有某种方法在有限的的所有对象都必须能够有某种方法在有限的时间内构造出来。因此塑造计算机系统的基时间内构造出来。因此塑造计算机系统的基本思维是本思维是构造性思维构造性思维。以上描述了计算理论的学科定位以上描述了计算理论的学科定位下面我们来看相关的历史人物简介下面我们来看相关的历史人物简介计算理论的开拓者计算理论的开拓者计算理论的开拓者计算理论的开拓者图灵图灵图灵图灵
22、阿兰阿兰图灵，图灵，19121912年年6 6月月2323日出生于英国伦敦。其祖日出生于英国伦敦。其祖父曾获得剑桥大学数学荣誉学位，但他父亲的数学才能平父曾获得剑桥大学数学荣誉学位，但他父亲的数学才能平平。因此，图灵的家庭教育，对他以后在数学及计算机方平。因此，图灵的家庭教育，对他以后在数学及计算机方面的成就并没有多少帮助。面的成就并没有多少帮助。小时侯的图灵生性活泼好动，很早就表现出对科学的小时侯的图灵生性活泼好动，很早就表现出对科学的探索精神。据他母亲回忆，探索精神。据他母亲回忆，3 3岁时，小图灵就进行了他的岁时，小图灵就进行了他的首次实验，尝试把一个玩具木头人的小胳膊、小腿掰下来首次实
23、验，尝试把一个玩具木头人的小胳膊、小腿掰下来栽到花园里，等待长出更多的木头人。到了栽到花园里，等待长出更多的木头人。到了8 8岁，他更开岁，他更开始尝试写一部科学著作，题目为关于一种显微镜。在这部很短的书中，始尝试写一部科学著作，题目为关于一种显微镜。在这部很短的书中，天才儿童图灵拼错了很多单词，句法也有些问题，但写得还能让人看懂，很天才儿童图灵拼错了很多单词，句法也有些问题，但写得还能让人看懂，很像那么一回事儿。在书的开头和结尾，他都用同一句话像那么一回事儿。在书的开头和结尾，他都用同一句话“首先你必须知道光首先你必须知道光是直的是直的”作前后呼应，但中间的内容却很短，短得破了科学著作的记录
24、。图作前后呼应，但中间的内容却很短，短得破了科学著作的记录。图灵曾说灵曾说:“:“我似乎总想从最普通的东西中弄出些名堂。我似乎总想从最普通的东西中弄出些名堂。”就连和小朋友们玩就连和小朋友们玩足球，他也能放弃当前锋进球这样出风头的事，只喜欢在场外巡边，因为这足球，他也能放弃当前锋进球这样出风头的事，只喜欢在场外巡边，因为这样能有机会去计算球飞出边界的角度。他的老师认为样能有机会去计算球飞出边界的角度。他的老师认为:“:“图灵的头脑思维可图灵的头脑思维可以像袋鼠一样进行跳跃。以像袋鼠一样进行跳跃。”图灵是个天才。他图灵是个天才。他1616岁就开始研究爱因斯坦的相对论。岁就开始研究爱因斯坦的相对论
25、。19311931年，图灵考入剑桥大学国王学院，开始他的数学生年，图灵考入剑桥大学国王学院，开始他的数学生涯，研究量子力学、概率论和逻辑学。在校期间，图灵涯，研究量子力学、概率论和逻辑学。在校期间，图灵还是现代语言哲学大师维特根斯坦班上最出色的学生。还是现代语言哲学大师维特根斯坦班上最出色的学生。他对由剑桥大学的罗素和怀特海创立的数理逻辑很感兴他对由剑桥大学的罗素和怀特海创立的数理逻辑很感兴趣。数理逻辑的创建，主要是为了对付趣。数理逻辑的创建，主要是为了对付“悖论悖论”。“悖悖论论”(”(paradox)paradox)是人类思维中最狡猾的两面派，最早起是人类思维中最狡猾的两面派，最早起源于古
26、希腊克里特岛上有个叫爱皮梅尼特的源于古希腊克里特岛上有个叫爱皮梅尼特的“智者智者”，他说他说:“:“所有的克里特岛人都说谎所有的克里特岛人都说谎”。我们可以把它简。我们可以把它简化为化为:“:“我说的这句话是假话我说的这句话是假话”。这就出现一种两面都。这就出现一种两面都无法自圆的怪圈无法自圆的怪圈:如果他没有说谎，那他这句话是错的，如果他没有说谎，那他这句话是错的，他是在说谎他是在说谎;如果他真的在说谎，那他说自己在说谎是如果他真的在说谎，那他说自己在说谎是对的，所以他又没有说谎。罗素和怀特海把它从逻辑、对的，所以他又没有说谎。罗素和怀特海把它从逻辑、集合论以及数论中驱逐出去，最后又想尽办法
27、归入数集合论以及数论中驱逐出去，最后又想尽办法归入数学原理之中。学原理之中。图灵一上大学，就迷上了数学原理。在图灵一上大学，就迷上了数学原理。在19311931年，著名的年，著名的“哥德尔定理哥德尔定理”出现后出现后(该定理认为没该定理认为没有一种公理系统可以导出数论中所有的真实命题，有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论除非这种系统本身就有悖论)，天才的图灵在数理，天才的图灵在数理逻辑大本营的剑桥大学提出一个设想逻辑大本营的剑桥大学提出一个设想:能否有这能否有这样一台机器，通过某种一般的机械步骤，能在原样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解
28、决所有的数学问题。则上一个接一个地解决所有的数学问题。大学毕业后，图灵去美国普林斯顿大学攻读博士大学毕业后，图灵去美国普林斯顿大学攻读博士学位，还顺手发明过一个解码器。在那里，他遇学位，还顺手发明过一个解码器。在那里，他遇见了冯见了冯诺依曼，后者对他的论文击节赞赏，并诺依曼，后者对他的论文击节赞赏，并随后由此提出了随后由此提出了“存储程序存储程序”概念。图灵学成后概念。图灵学成后又回到他的母校任教。在短短的时间里，图灵就又回到他的母校任教。在短短的时间里，图灵就发表了几篇很有份量的数学论文，为他赢得了很发表了几篇很有份量的数学论文，为他赢得了很大的声誉。大的声誉。在剑桥，图灵可称得上是一个怪才
29、，一举一动常常在剑桥，图灵可称得上是一个怪才，一举一动常常出人意料。他是个单身汉和长跑运动员。在他的同事和出人意料。他是个单身汉和长跑运动员。在他的同事和学生中间，这位衣着随便、不打领带的著名教授，不善学生中间，这位衣着随便、不打领带的著名教授，不善言辞，有些木讷、害羞，常咬指甲，但他更多地以自己言辞，有些木讷、害羞，常咬指甲，但他更多地以自己杰出的才智赢得了人们的敬意。图灵每天骑自行车上班，杰出的才智赢得了人们的敬意。图灵每天骑自行车上班，因为患过敏性鼻炎，一遇到花粉，就会鼻涕不止，大打因为患过敏性鼻炎，一遇到花粉，就会鼻涕不止，大打喷嚏。于是，他就常常在上班途中戴防毒面具，招摇过喷嚏。于是
30、，他就常常在上班途中戴防毒面具，招摇过市，这早已成为剑桥的一大奇观。图灵的自行车经常半市，这早已成为剑桥的一大奇观。图灵的自行车经常半路掉链子，但他就是不肯去车铺修理。每次骑车时，他路掉链子，但他就是不肯去车铺修理。每次骑车时，他总是嘴里念念有词，在心里细细计算，这链条也怪，总总是嘴里念念有词，在心里细细计算，这链条也怪，总是转到一定的圈数就滑落了，而图灵竟然能够做到在链是转到一定的圈数就滑落了，而图灵竟然能够做到在链条下滑前一刹那停车，让旁观者佩服不已，以为图灵在条下滑前一刹那停车，让旁观者佩服不已，以为图灵在玩杂技。后来图灵又居然在脚踏车旁装了一个小巧的机玩杂技。后来图灵又居然在脚踏车旁装
31、了一个小巧的机械记数器，到圈数时就停，歇口气换换脑子，再重新运械记数器，到圈数时就停，歇口气换换脑子，再重新运动起来。动起来。19361936年，图灵向伦敦权威的数学杂志投了一篇论文，题为年，图灵向伦敦权威的数学杂志投了一篇论文，题为论数字计算在决断难题中的应用。在这篇开创性的论文论数字计算在决断难题中的应用。在这篇开创性的论文中，图灵给中，图灵给“可计算性可计算性”下了一个严格的数学定义，并提出下了一个严格的数学定义，并提出著名的著名的“图灵机图灵机”(”(Turing Machine)Turing Machine)的设想。的设想。“图灵机图灵机”不不是一种具体的机器，而是一种思想模型，可制
32、造一种十分简是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。装置由一个控制器和一根假设两端无界的工的可计算函数。装置由一个控制器和一根假设两端无界的工作带作带(起存储器的作用起存储器的作用)组成。工作带被划分为大小相同的方组成。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写头，可读出控制器所访问在带上左右移动，它带有一个读写头，可读出控制器所访问的格子上的符号，
33、也能改写或抹去这一符号，最后便会得出的格子上的符号，也能改写或抹去这一符号，最后便会得出一个你期待的结果。外行人看了会坠入云里雾里，而内行人一个你期待的结果。外行人看了会坠入云里雾里，而内行人则称它是则称它是“阐明现代电脑原理的开山之作阐明现代电脑原理的开山之作”，并冠以，并冠以“理想理想计算机计算机”的名称。这篇论文在纸上谈了一把兵，创造出一个的名称。这篇论文在纸上谈了一把兵，创造出一个“图灵机图灵机”来。但现代通用电脑确实是用相应的程序来完成来。但现代通用电脑确实是用相应的程序来完成任何设定好的任务。这一理论奠定了整个现代计算机的理论任何设定好的任务。这一理论奠定了整个现代计算机的理论基础
34、。基础。“图灵机图灵机”更在电脑史上与更在电脑史上与“冯冯诺依曼机诺依曼机”齐名，齐名，被永远载入计算机的发展史中。被永远载入计算机的发展史中。1931年，年轻的法国数学家赫尔布兰德年，年轻的法国数学家赫尔布兰德（Jacques Herbrand，19081931）对）对递归函数进行了研究，并给著名逻辑学家哥递归函数进行了研究，并给著名逻辑学家哥德尔（德尔（Kurt Gdel，19061978）写信叙）写信叙述了自己的研究结果。哥德尔当时正处于自述了自己的研究结果。哥德尔当时正处于自己一生中最重大的成果己一生中最重大的成果哥德尔不完全性定哥德尔不完全性定理的研究时期，他没有仔细看赫尔布兰德的理
35、的研究时期，他没有仔细看赫尔布兰德的来信内容，因此没有立即对赫尔布兰德的工来信内容，因此没有立即对赫尔布兰德的工作做出回应。那一年的夏天，年仅作做出回应。那一年的夏天，年仅23岁的岁的赫尔布兰德在攀登阿尔卑斯山时不幸遇难，赫尔布兰德在攀登阿尔卑斯山时不幸遇难，他的工作因此被暂时埋没了。他的工作因此被暂时埋没了。与赫尔布兰德的研究差不多同时，与赫尔布兰德的研究差不多同时，1931年秋天，普林斯年秋天，普林斯顿大学的美国逻辑学家丘奇（顿大学的美国逻辑学家丘奇（Alonzo Church，19031995）也在积极从事逻辑及算法的研究，并且发展出了一种）也在积极从事逻辑及算法的研究，并且发展出了一种
36、新的逻辑体系。丘奇在普林斯顿开了一门逻辑课，他让自己的新的逻辑体系。丘奇在普林斯顿开了一门逻辑课，他让自己的两个学生克林（两个学生克林（Stephen Kleene，19091994）与罗瑟）与罗瑟（John Rosser，19071989）对这一体系做细致的研究。）对这一体系做细致的研究。两个学生都是一流好手，他们的研究很快就有了结果，但这结两个学生都是一流好手，他们的研究很快就有了结果，但这结果大大出乎丘奇的意料。他们发现丘奇的那套体系竟然是自相果大大出乎丘奇的意料。他们发现丘奇的那套体系竟然是自相矛盾的！命运似乎只有一个：放弃。幸运的是，丘奇的那套体矛盾的！命运似乎只有一个：放弃。幸运的
37、是，丘奇的那套体系中有一个组成部分是自洽的，因此可以保留下来，这部分叫系中有一个组成部分是自洽的，因此可以保留下来，这部分叫做兰姆达运算（做兰姆达运算（calculus）。这种兰姆达运算可以用来定义）。这种兰姆达运算可以用来定义函数，而所有用兰姆达运算定义的函数都是可以有效计算的。函数，而所有用兰姆达运算定义的函数都是可以有效计算的。在对兰姆达运算做了研究之后，丘奇提出了一个大胆的猜测，在对兰姆达运算做了研究之后，丘奇提出了一个大胆的猜测，他猜测所有可以有效计算的函数都可以用兰姆达运算来定义。他猜测所有可以有效计算的函数都可以用兰姆达运算来定义。于是克林开始进行研究，结果克林和丘奇得到一类可计
38、算的函于是克林开始进行研究，结果克林和丘奇得到一类可计算的函数，他们称之为数，他们称之为A可定义函数。可定义函数。1934年春天，哥德尔在普林斯顿大学做了一系列讲年春天，哥德尔在普林斯顿大学做了一系列讲演。丘奇向到普林斯顿大学访问的哥德尔介绍了他的演。丘奇向到普林斯顿大学访问的哥德尔介绍了他的猜测，哥德尔却不以为然。丘奇不服气，请哥德尔给猜测，哥德尔却不以为然。丘奇不服气，请哥德尔给出一个他认为合适的描述。一两个月后，哥德尔就给出一个他认为合适的描述。一两个月后，哥德尔就给出了一种完全不同的描述，这种描述的基础正是出了一种完全不同的描述，这种描述的基础正是3年年前赫尔布兰德在给他的信中叙述的结
39、果。哥德尔对这前赫尔布兰德在给他的信中叙述的结果。哥德尔对这一结果进行了完善，这一结果被人们称为赫尔布兰德一结果进行了完善，这一结果被人们称为赫尔布兰德哥德尔递归函数。与此同时，丘奇和克林在哥德尔递归函数。与此同时，丘奇和克林在1936年分别发表论文，证明年分别发表论文，证明A可定义函数类正好就是一般可定义函数类正好就是一般递归函数类。递归函数类。有了这个有力的证据，丘奇于是公开发有了这个有力的证据，丘奇于是公开发表他的表他的论点论点。这样，丘奇与哥德尔各自给出了一种。这样，丘奇与哥德尔各自给出了一种体系，描述可以有效计算的函数。丘奇与克林很快证体系，描述可以有效计算的函数。丘奇与克林很快证明
40、，这两种看上去完全不同的描述方式实际上是彼此明，这两种看上去完全不同的描述方式实际上是彼此等价的。等价的。两位著名逻辑学家的工作殊途同归，大大增强了丘奇的信心。他相信人们已经找到了可以有效计算的函数的普遍定义。但哥德尔及其他一些人对此却仍然怀有疑虑。最终打消这种疑虑的是英国数学家图灵（Alan Turing，19121954）。1937年图灵证明了用图灵机可计算的函数类与可定义函数类是一致的，当然，也就和一般递归函数类相重合。这样一来，丘奇的论点与图林的论点就是一回事。当时许多人对于丘奇的论点表示怀疑，由于图林的思想表述得如此清楚，从而消除了许多人的疑虑，哥德尔就是其中一位。从这时起大家对于丘
41、奇-图灵论点一般都抱支持的态度了。数理逻辑学家歌德尔1947年美国数学家波斯特（年美国数学家波斯特（Emil Post，18971954）找到了第一个逻辑领域以外的不可判定命题。波斯特是一位有找到了第一个逻辑领域以外的不可判定命题。波斯特是一位有着深刻洞察力的逻辑学家，着深刻洞察力的逻辑学家，7岁时随父母从波兰移民到美国，岁时随父母从波兰移民到美国，是美国逻辑学的先驱之一。他是美国逻辑学的先驱之一。他10年前就得到了与哥德尔不完年前就得到了与哥德尔不完全性定理相似的结果，由于想对结果作更全面的分析而没有及全性定理相似的结果，由于想对结果作更全面的分析而没有及时发表。他也是最早意识到希尔伯特第十
42、问题可能会有否定答时发表。他也是最早意识到希尔伯特第十问题可能会有否定答案的数学家之一。案的数学家之一。1944年，他在一篇文章中明确提出希尔伯年，他在一篇文章中明确提出希尔伯特第十问题特第十问题“期待一个不可解性证明期待一个不可解性证明”。当时波斯特在纽约市。当时波斯特在纽约市立大学任教，他的这一观点深深打动了一位学生，使后者走上立大学任教，他的这一观点深深打动了一位学生，使后者走上了毕生钻研希尔伯特第十问题的征途。这位学生名叫戴维斯了毕生钻研希尔伯特第十问题的征途。这位学生名叫戴维斯（Martin Davis，1928），是解决希尔伯特第十问题的关），是解决希尔伯特第十问题的关键人物。键人
43、物。图灵奖与计算理论图灵奖与计算理论图灵奖是由ACM于1966年首次设立的奖项,它是为了纪念“计算机科学之父”图灵而设立的,专门奖励那些在计算机科学研究中做出创造性贡献、推动了计算机科学技术发展的杰出科学家。虽然没有明确规定，但从实际执行过程来看，图灵图灵奖偏重于在计算机科学理论和软件方面作出贡献的科学家奖偏重于在计算机科学理论和软件方面作出贡献的科学家。奖金金额不算太高，设奖初期为2万美元，1989年增至2万5千美元，奖金通常由计算机界的一些大企业提供（通过与ACM签定协议）。由于图灵奖对获奖者要求极高，评奖程序又极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作
44、出贡献的科学家共享此奖。因此它是计算机界最负盛名、最崇高的一个奖项，有计算机界的诺贝尔奖“之称。从1966年到2000年共有41位科学家获此殊荣，在这些学者中从事计算复杂性理论研究的有11人，几乎占四分之一。他们是？1976年图灵奖获得者年图灵奖获得者拉宾和斯科特拉宾和斯科特1976年的图灵奖由当时在以色列希伯莱大学的教授拉宾和英国牛津大学的数理逻辑教授斯科特共同获得。他们是师兄弟，两人在两人在5050年代中期先后师从于著名的数理逻辑与计算机科学年代中期先后师从于著名的数理逻辑与计算机科学家丘奇家丘奇（他对可计算性理论做出了实质性贡献，如判定问题的解、演算的发明，90岁还在发表论文，图灵也是他
45、的学生），并在有限自动机及其判定问题的研究中进行合作，奠定了非确定性有限自动机的理论基础，之后，他们的研究方向不尽相同，拉宾侧重于计算理论，而斯科特侧重于逻辑学在计算机科学中的应用，在各自的领域中又分别获得重大成果，做出了创造性贡献。计算机科学家、数理逻辑学家丘奇拉宾是1931年出生于德国的布雷斯劳的犹太人，1948年以色列建国以后成为以色列公民，20世纪50年代拉宾博士毕业于普林斯顿大学，使拉宾成名的是IBM研究中心1957年向他和师弟斯科特提供的允许他们做自己感兴趣的工作。于是他们二人联手研究图灵机-有限状态自动机。他们定义了一种新的、“非确定性”行为的有限状态自动机(NDFSA)，这种机
46、器在读去到一定的输入后，有一个可以进入的可能的新的状态的菜单可供选择，这样对给定的输入计算便不单一了，每个选择代表一种可能的计算。拉宾和斯科特将图灵的有限状态自动机从确定性一种扩展到非确定的另一种形式，极大地推动了有限状态自动机理论的发展，虽然非确定性有限状态自动机的能力并不比确定性的有任何增加（拉宾和斯科特已经证明他们等价），但是它可以简化机器描述和加快解题速度。后来的时间证明，非确定性有限状态自动机在机器翻译、文献检索和字处理程序等应用中都起到了重要作用。他们的研究结果发表于2年后的1959年IBM杂志上，题目为“有限自动机及其判定问题”。1958年夏天拉宾又来到IBM，当时“人工智能之父
47、”麦卡锡（1971年图灵奖获得者）正在那里研究往巴克斯（1977年图灵奖获得者）发明的FORTRAN语言中加入表处理功能，他给拉宾出了一道难题：设计一种口令即使口令被敌方窃取，也无法进入系统。拉宾经过艰苦探索，终于利用冯诺伊曼开发的一个单向函数解决了这个问题。正是这个问题促使拉宾进一步研究计算任务的最小计算量这一一般性问题，也就是计算的固有难度问题，从而使拉宾成为最早研究计算复杂性问题的先驱之一。他的研究结果“计算速度和递归集合的分类”与“函数的计算难度和递归集合的偏序”分别于1959和1960年在耶路撒冷发表。论文中虽然没有用“计算复杂性这个名词而用了”计算速度“和”计算难度“，但学术界公认
48、这两篇论文是研究计算复杂性的最早、最权威的论文中的两篇，对1964年正式提出”计算复杂性“这一术语的哈特马尼斯和斯特恩斯（这2人是1993年图灵奖获得者，后面介绍）以及计算复杂性理论的另一奠基人布卢姆（1995年图灵奖获得者，后面介绍）都产生了深刻影响。其中布卢姆正是听到了拉宾的有关演讲才开始研究计算复杂性并完成博士论文的。斯科特比拉宾小一岁，1932年出生于加利福尼亚，在加州大学伯克利分校获得学士学位后，进入普林斯顿大学研究生院深造，与拉宾一起师从于阿隆索丘齐。丘齐对学生要求很严，布置的问题也很难，斯科特开始时难以适应，精神很紧张，经常夜里作恶梦。但经过努力，终于可以从容应付。1957年他与
49、师兄拉宾一起完成了对图灵机的研究，提出了非确定性有限状态自动机的理论以后，在1958年取得博士学位。之后他先后在芝加哥大学、加州大学伯克利分校、斯坦福大学、普林斯顿大学和牛津大学等国际知名高等学府任教。1981年被卡内基梅隆大学聘为计算机科学、数理逻辑和哲学教授。斯科特的主要兴趣和研究方向是逻辑学，包括集合论、模型论、自动机理论、非经典逻辑中的模态逻辑和直觉主义逻辑。斯科特的最大贡献是他与斯特雷奇合作，20世纪60年代提出了程序设计语言的“标志语义模型”为标志语义学奠定了坚实的基础。1978年图灵奖获得者年图灵奖获得者弗洛伊德弗洛伊德历届图灵奖得主基本上都有高学历、高学位，绝大多数都有博士学位
50、，但事情总有例外，1978年图灵奖得主、斯坦福大斯坦福大学计算机科学系教授弗洛伊德就是一位学计算机科学系教授弗洛伊德就是一位“自学成才的计算机自学成才的计算机科学家科学家”。说他自学成才并不是说他没有接受过高等教育，他是芝加哥大学的毕业生，但学的是文学，1953年获得文学学位，由于当时经济不景气，成为西屋电气公司一名计算机操作员，他不懂计算机，但是个有心人，受过良好高等教育很快对计算机产生了兴趣开始学习相关知识，1956年成为程序员，1965年被卡内基-梅隆大学聘为副教授，1970年聘为教授。大家现在熟知的优先文法，界限上下文文法都大家现在熟知的优先文法，界限上下文文法都是他是他20世纪世纪6