[计算机模型.doc

前言： 话说梦想关于计算机有一天能像人一样思考的科幻作品是一个已经比较古老的主题了。甚至还有人专门设计了的类似“机械人三原则”之类的具体设想，以此来分析将来计算机智能一旦发展到人的智商我们究竟会面临哪些问题。 不过对于另一些科学家来说，往往他们考虑问题的深度可能不够，他们通常更多的是先考虑如何实现某个技术，至于实现该技术后带来的一切社会、政治问题他们都先不作考虑。我想大概研究武器的科学家比较突出吧。总而言之，无论计算机智能高度发展可能带来什么样的危机。能够实现计算机高度拟人化思维的设想永远是计算机研究者的一个梦想。 然而，计算机本身是否具有能像人一样思考的潜力呢？计算机想要模拟人的思考方式究竟要向那些方向发展呢？我在学习了计算机运算原理之后得到了很大的启示。在此跟大家分享一下，好引起激烈争论，活跃论坛气氛。 PS:本人向来拒绝一切用高深词汇和难以理解的专用名词把一个本来容易理解的问题变得难以接受。下面的内容我尽量的用浅显的道理解释。特别是希腊字母我又打不出来，因此涉及专门的数学证明的地方有兴趣的朋友可以参考相关资料。 1，什么是计算机的运算原理（Theory of computation） 所谓运算原理，或者计算原理。就是研究计算机究竟是用什么方法来工作的。通过理解计算机的工作方法，我们可以推断出计算机究竟能做什么和不能做什么。以及用什么方法才能完成某些工作。这就相当于我们研究一下收音机是如何工作的，就能知道收音机能接受什么信号，不能接受什么信号。 计算机科学虽然发展的越来越快，计算机的性能从数字上越来越高。但是仍然有些事情是单靠发展计算机性能无法实现的。就好像你加大收音机的接受频段，也不可能打出一张X光相片一样。 这里需要指出一点，对于有一定编程基础的朋友而言要区分计算机运算原理并不是计算机算法原理。所谓算法，大家都清楚，是用一个类似程序的流程方法把程序表述出来。比如排序算法，你可以选择大数往后排，或者小的数字往前排。然后考虑一下哪种算法在哪种情况下运行效率比较高，哪种算法存储空间效率比较高等等。计算原理完全是另一个概念，它往往不会具体到某一个算法，它可以告诉你计算机“能”或“不能”执行某一种任务。以及一旦要执行一个非常困难的任务，我们应该向哪个方向考虑。这里面更多的是用数学的概念来进行推导和证明。 那么为了研究计算机的运算方法，我们把计算机简化成为几种非常简单的模型。根复杂的计算机系统比，这些模型看起来可以用简陋形容。但是他们对于我们理解计算机的能力却又是必不可少的工具。 计算机的简单模型主要分为三种：有限状态自动机Finite Automaton（FA），下推自动机Push Down Automaton(PDA)，以及图灵机Turing machine。这三种模型一个比一个复杂，一个比一个功能更强大。当然这些名词看起来有点玄。我马上用简单的语言给大家解释一下。 2，有限状态自动机（简称FA） 所谓自动机，其实就是不需要人为干预指可以自动执行某个任务的机器。说白了也就是计算机。那么有限状态是指什么呢？就是说这种计算机没有任何动态的存储设备。他不能记录任何数据。因此他的限制很大。 比如说有什么限制呢?他连最简单的数绵羊的任务都执行不了。因为数绵羊随着数字逐渐增加，数字位数逐渐增大，你就需要更多的空间来存储数字。但是因为存储空间有限，数字增大到一定程度必然超过你“有限”的状态。因此他不能执行数绵羊的任务。 需要注意的是，这里有一个可能抬杠的地方，就是大多数程序员都知道计算机的存储空间其实都是有限的，不可能执行一个无限数绵羊的程序。我必须强调一下，所谓有限状态，是指你写好这个程序之后，它就有固定的状态个数了，你无论如何改变计算机性能都无法增加状态的个数。比如说：如果你用高级的方法写一个数绵羊的程序，你现在内存只有1G，当你数到把1G内存都沾满之后就不能继续数了。但是你把内存换成2G就又可以继续数了。但是有限状态的自动机，如果在你程序写好的时候有100个状态，那么你无论增加多少内存，增加多少存储空间，它永远都是100个状态。不会动态的增加和减少。因此我们在这个简化模型中称他的状态“有限”。类似的，以后涉及到有存储空间的其他模型时候，我们都是假设他们的存储空间“无限”，因为他们可用的存储空间能够随着计算机性能的提高而不断的动态增加。 那么FA究竟能执行什么任务呢，他可以执行一些简单的逻辑任务，比如一个控制开门的机器。输入ABCD就开门，其他的输入就不开。那么简化的说就可以设计一个4个状态的自动机，当输入A，就进入状态1，输入B进入状态2，输入C进入状态3，输入D进入接受状态。而在1，2，3任意一个状态里，后面如果跟着的不是我们所期待的密码。比如A后面跟着C，或者AB后面跟着F，这样的错误输入我们就退回