数理逻辑(姜伟)10-2.2算法复杂性.ppt

图灵试验一个人在不接触对方的情况下，通过一种特殊的方式，和对方进行一系列的问答，如果在相当长时间内，他无法根据这些问题判断对方是人还是计算机，那么，就可以认为这个计算机具有同人相当的智力，即这台计算机是能思维的。问：34957加70764等于多少？答：（停30秒后）105721问：你会下国际象棋吗？答：是的。图灵试验从表面上看，要使机器回答按一定范围提出的问题似乎没有什么困难，可以通过编制特殊的程序来实现。然而，如果提问者并不遵循常规标准，编制回答的程序是极其困难的事情。问：你会下国际象棋吗？答：是的。问：你会下国际象棋吗？答：是的。问：请再次回答，你会下国际象棋吗？答：是的。问：你会下国际象棋吗？

答：是的。问：你会下国际象棋吗？

答：是的，我不是已经说过了吗？问：请再次回答，你会下国际象棋吗？

答：烦不烦，干嘛老提同样的问题。图灵机从读写头在纸带上读出一个方格的信息，并且根据它当前的内部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移动读写头到下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。这个装置包括：一个无限长的纸带，一个读写头，内部状态，另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。具体的程序就是一个列表，也叫做规则表，是这样的：图灵机当前内部状态s输入数值i输出动作o下一时刻的内部状态sB1前移CA0往纸带上写1BC0后移A…………0304050102图灵机也许，你会觉得图灵机模型太简单，怎么可能完成计算机的复杂任务呢？问题的关键是如何理解这个模型。图灵机就是这么简单！不可思议吧？而只要你变化它的程序（也就是上面的规则表），那么它就可能为你做任何计算机能够完成的工作。因此可以说，图灵机就是一个最简单的计算机模型！图灵机假设一个小虫在地上爬，那么我们应该怎样从小虫信息处理的角度来建立它的模型？首先，我们需要对小虫所在的环境进行建模。假设小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小的方格，而每个方格都仅仅只有黑和白两种颜色。小虫要有眼睛或者鼻子或者耳朵等等感觉器官来获得世界的信息，我们不妨把模型简化，假设它仅仅具有一个感觉器官：眼睛，而且它的视力短得可怜，也就是说它仅仅能够感受到它所处的方格的颜色。因而这个方格所在的位置的黑色或者白色的信息就是小虫的输入信息。图灵机另外，我们还需要为小虫建立输出装置，也就是说它能够动起来。我们仍然考虑最简单的情况：小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格。仅仅有了输入装置以及输出装置，小虫还不能动起来，原因很简单，它并不知道该怎样在各种情况下选择它的输出动作。我们还需要给它指定行动的规则，这就是程序！假设我们记小虫的输入信息集合为I={黑色，白色}，它的输出可能行动的集合就是：O={前移，后移}，那么程序就是要告诉它在给定了输入比如黑的情况下，它应该选择什么输出。图灵机程序1：输入输出黑色前移白色后移小虫所处的世界的一个片断是：黑黑黑白白黑白图灵机比如虫子看到旁边有食物，它就会把那个东西吃掉了。在我们这个模型中，也就相当于小虫可以改写纸带上的信息。因而，小虫可能的输出动作集合就变成了：O={前移，后移，涂黑，涂白}。我们知道小虫除了可以机械地在世界上移动以外，还会对世界本身造成影响，因而改变这个世界。然而，现实世界中的小虫肯定不会这样傻的在那里无限循环下去。我们还需要改进这个最简单的模型。图灵机程序2：输入输出黑前移白涂黑纸带是黑黑白白黑，小虫会怎样行动呢？图灵机你还可以设计出其他的程序来，然而无论你的程序怎么复杂，也无论纸带子的情况如何，小虫的行为都会要么停留在一个方格上，要么朝一个方向永远运动下去，或者就是在几个方格上来回打转。无论怎样，小虫比起真实世界中的虫子来说，还有一个致命的弱点：那就是如果你给它固定的输入信息，它都会给你固定的输出信息！因为我们知道程序是固死的。图灵机小虫具有两个内部状态，并把它内部状态的集合记为：S={饥饿，吃饱}。假设黑色方格是食物，虫子可以吃掉它，而当吃到一个食物后，小虫子就会感觉到饱了。当读入的信息是白色方格的时候，虽然没有食物但它仍然吃饱了，只有当再次读入黑色时候它才会感觉到自己饥饿了。我们进一步更改小虫模型，至少在给定相同输入的情况下，小虫会有不同的输出情况。这就是加入小虫的内部状态！数理逻辑MathematicalLogic第二章算