admin 1
任何工具都只能在人类的驱使下做特定的事情，计算机也不例外。否则就不能称之为工具，而成为哲学意义上的具有主体自觉性的存在了。
就现代计算机而言，人类驱使计算机所做的底层的，并且对人类具有直接意义的事情，便是有限字长的二进制数字的算数与逻辑运算，以及对它们的存储。算数运算最基本的是加法，减、乘和除法都可以用加法来实现。但在讨论中把它们都作为基本计算并不会失去一般性。逻辑运算就是与、或、非和异或。我们把这些运算简称为基本计算。换句话说，人类通过自己的智能设计，使得计算机具有了对有限字长二进制数字的基本计算能力，以及相应的存储能力。这是计算机底层内置和预置的、对人类具有基础性意义，并且是大众化可理解的能力。
在此基础上，人类可以通过更复杂的硬件功能，特别是软件程序将更多上层的功能预置在计算机内，进一步驱使计算机做更为复杂的事情，使得计算机表现出更复杂、对人类有直接可理解意义的功能。比如字符处理能力、函数计算能力、图像识别能力、以及其他复杂的信息处理能力等等。但是，在计算机内部，在它的底层，计算机所具有的人类一般意义上可理解的能力，其实仅仅是有限字长二进制数字的基本计算能力以及存储能力。
作为人类辅助智能的工具，有限字长二进制数字的基本计算和存储能力，是计算机介入人类智能活动的第一层，同时它也是计算机更进一步介入人类智能活动的基础。因此可以方便地将其作为起点与基础，来分析计算机能够对人类智能活动介入的深度和范围。它是我们理解计算机能做什么与不能做什么的核心与关键。而计算机内部为了实现计算功能等，发生的更为底层的操作过程和物理过程，对我们来说并不重要。它们与人类的智能活动没有直接的联系。而将分析建立在计算机更上层的功能之上，则有可能失去计算机的本质内涵。
这也是艾伦•图灵（1912-1954，数学家、逻辑学家、密码学家，剑桥大学任职）在1936年设计图灵机的初衷。图灵机不关心如何用具体的技术手段实现计算能力，只是在纯逻辑层面描述最基本的计算过程，尽管这个过程比我们前面说的基本计算更为基本一些，但本质是一样的。在现实中，为了实现这个过程而需要发生的物质变化过程，不在图灵机考虑范围之内。图灵机的意义就在于用这些基本的功能，来分析哪些问题是通过图灵机（计算）可以解决的。而现代计算机可以解释为抽象的图灵机的一种具体实现形式。
艾伦•图灵的天才表现在迄今为止，人类机械物理性（非生命性）工具介入人类智能活动的第一步，也是最基本的一步，始终是有限字长二进制数字的基本计算，并没有找到其他不同的或更为基本的起点。所以，我们至今为止，都将艾伦•图灵作为人类现代辅助智能类工具的鼻祖。这或许是图灵的远见，或许只是巧合。有重大意义的巧合，其实也是一种天才的表现。
现代计算机的这种基本计算能力，是人类智力物化/外化的结果，或者说是人类智力设计的结果。人类今天外化了更多的智力过程（典型的就是不同的软件），但是都是建立在这个基础上的。
人类之所以可以物化数字的基本计算过程，是因为数字的基本计算，是人类精神智力活动中有着严格无歧义、确定性、逻辑化操作的过程。这个属性与宏观物质世界中的机械物理类运动规律的基本特性有着高度的一致。所以，对数字的基本计算成为了人类可以用机械物理类运动来实现的智能化活动。而且，也是迄今为止唯一可以有效地被物化的人类最为基础的智力活动。
数字的基本计算所具有的严格的无歧义、确定性、逻辑化操作特性，在一般意义上构成了计算机可以解决的问题的基本特征。这是我们在判断哪些问题可以用计算机来解决的一个重要依据。
物质世界的运动规律并不是都符合基本数字计算的上述特征。微观的量子活动，就具有不确定性和多义性。这是否会构成另外一类的人类智力活动被物化的基础，目前尚未可知。如果量子计算与人类智能活动的结合点依然是基本的数字计算的话，那量子计算带来的无非是计算性能的强化，并没有质的飞跃；如果借助量子效应，量子计算能够找到基本数字计算之外的与人的智能活动新的结合点，并且依赖这个结合点能够支撑更多的人类智能活动的话，那量子计算将引发人类创造的辅助智能类工具的革命性突破。假如未来造出这样的计算机，那它的理论基础，将不是以图灵机为代表的现在的这些理论了。
2
德国数学家大卫*希尔伯特在1928年提出“可判定性问题”（其名的二十三个希尔伯特问题之一），用门外汉的话说，“可判定性问题”指是否有这样一个程序（或者算法）可以或能够证明一个数学陈述是正确还是错误的。对当时的数学家来说，“可判定性问题”看起来很像是一个心理学、认识学或神学问题。阿兰*图灵对这个问题的答案是“没有”－－并没有这样一个算法来证明所有的数学陈述是否正确。在美国普林斯顿任职的数学家阿隆佐*邱奇比图灵早几周发现这个答案。邱奇用微积分这样一种逻辑系统给这个问题提供了答案。图灵的答案充分发挥了他的想像力，他解决问题的方式和阿塔纳索夫有点类似－－他在康河河岸跑步的时候找到了灵感。他是一个热爱跑步的人，有时候一直往北跑到离剑桥二十英里的伊莱。一天，他跑累了在草地上休息的时候，突然想到一个简单的程序，或者说是一串指令，能让机器运转起来。
他在论文中写到了这个方法，图灵描述了做一个简单但是很艰难的心理过程。他想像做计算的这个人被给予了一系列的指令，如果她每次都能按照指令来完成工作，她的大脑会一直以同一种方式思考，这样就不会犯计算错误（尽管这项工作会无比的枯燥无味）。很快。图灵就从一系列的指令联想到了一个完美的机器设想－－能够自己运行，不需要人工干预。它可以一直运行一些程序，这些只有有限数字的程序很容易被设定。他描述了一个装入了很长胶带的机器。胶带被分为几个正方形，每一个都有一个标记或是空白。当机器扫描任何一个有标记或没有标记的的方形时，它会被要求运行一个程序－－在空白的方形里填入标记，在有标记的方形里删除标记，然后右移一格或左移一格。每一个程序在运行完毕后，机器即可往前运行下一条指令，它扫描新的方形然后对这个方形按照指令进行操作－－指令应该和计算一起向前推进。这种演变被图灵称为“行为表”，我们称为程序。最终，机器到达了计算的终点－－例如，它可以根据行为表的指令在删除一个标记并往左移之后停下来。这样的操作显示已经求解出了答案－－如果有附加的问题，被标记的方形相加就是问题所列出的标记的总和。
图灵设想了解决那些能够解决和不能够解决的数学问题能够用到的所有机器。求解这些问题所需要的东西其实只是一系列的指令和时间（和一个包含符号和空格的二进制系统），如果可以解决一个问题，那么机器就可以一直运行到问题结束。如果不能解决，那么机器就会卡住－－一个错误的指令序列会让机器只能前进或后退，不停的消除并复制两个同样的方块。随后，图灵又想出了一个全面的机器，他称为“通用机器”，通过给机器足够的指令，能够解决所有特制机器能够解决的任何问题。他提出只要有足够的时间和指令，这样的机器是可以制造出来的。他解决“可判定性问题”的杀手锏是：设想他的机器如何能解决任何一个问题，他能很轻易地看到如何给机器一个能够让机器停止运转的指令的问题－－也就是说，让它不停地重复一项操作而不达成任何解决方案。唯一一个能确定问题能否解决的办法就是想尽一切办法解决它们。数学无法提前设计出一种方案预测任何一个问题是否能够被解决，因此，不一定能确定一个给定陈述的真实性。此外，尽管机器能不停地运转，但人们找不到一种让机器自查的办法。因此也无法确定机器给出的答案正确与否。
微积分“展现了抽象和变化的数学过程具有优雅和强大的象征意义”，但是图灵机是一种思想实验，设想的是一种机械装置，可以通过机械或者人的大脑来完成。图灵的传记作家安德鲁*哈吉斯指出，图灵的想法“不仅仅是抽象数学的问题，也不仅是一堆符号的游戏，因为它牵涉到人类在物理世界的所作所为的思考……他的机器－－不久后被称为图灵机－－是一座桥梁，连接抽象的符号和物理世界。他的创意对剑桥来说真是令人震惊的”。
1936年5月，阿兰*图灵向《伦敦数学协会会报》提交了一篇名为《论可计算数，可判定性应用》的论文，但是没能如愿申请到普贤林斯顿大学的普贤科特奖学金。对当时所有的英格兰人而言，只有图灵和美国的阿隆佐*邱奇才能解释可判定性。英格兰当时没人有资格给图灵或者邱奇的论文做评审。
阿塔纳索夫和图灵用各自不同的方式证明了计数是计算的未来，但是二人之间的差异也十分明显－－阿塔纳索夫需要发明一个实实在在的机器，开关一开就能运行有用的功能。图灵设想的是一种重复机械过程，但是由于他自己并不是一个喜欢搞小发明的人，他也没有从他那些有发明天赋的祖先那里继承到工程设计方面的天赋，他的机器最主要的作用是激发别人的发明灵感，而不是成为发明本身。
图灵机由一个控制器和一条两端可无限延长的工作带组成：工作带起着存储器的作用，它被划分为无穷多个可写可擦的方格。控制器则可以在带上左右移动，控制带有一个读写头，读写头可以读出当前方格内的符号，然后根据预先设计的状态转换指令，选择改写或抹去这一符号，然后选择往左移一格，往右移一格或者不移动，并进入下一个状态。当状态转换到停机状态，则停止运行。
图灵机的出现，奠定了计算机科学的理论基础，计算机的出现已经主要是技术实现的问题了。
所有的数学问题都可以归结为逻辑问题，而逻辑问题又可以通过电气开关表现出来。
3
“图灵机”想象使用一条无限长度的纸带子，带子上划分成许多格子。如果格里画条线，就代表“1”;空白的格子，则代表“0”。想象这个“计算机”还具有读写功能:既可以从带子上读出信息，也可以往带子上写信息。计算机仅有的运算功能是:每把纸带子向前移动一格，就把“1”变成“0”，或者把“0”变成“1”。“0”和“1”代表着在解决某个特定数学问题中的运算步骤。“图灵机”能够识别运算过程中每一步，并且能够按部就班地执行一系列的运算，直到获得最终答案。
“图灵机”是一个虚拟的“计算机”，完全忽略硬件状态，考虑的焦点是逻辑结构。图灵在他那篇著名的文章里，还进一步设计出被人们称为“万能图灵机”的模型，它可以模拟其他任何一台解决某个特定数学问题的“图灵机”的工作状态。他甚至还想象在带子上存储数据和程序。“万能图灵机”实际上就是现代通用计算机的最原始的模型。
图灵的文章从理论上证明了制造出通用计算机的可能性。几年之后，美国的阿坦纳索夫在1939年果然研究制造了世界上的第一台电子计算机ABC，其中采用了二进位制，电路的开与合分别代表数字0与1，运用电子管和电路执行逻辑运算等。ABC是“图灵机”的第一个硬件实现，看得见，摸得着。而冯•诺依曼不仅在上个世纪40年代研制成功了功能更好、用途更为广泛的电子计算机，并且为计算机设计了编码程序，还实现了运用纸带存储与输入。到此，天才图灵在1936年发表的科学预见和构思得以完全实现。
图灵当年那篇划时代的抽象数学论文，原本是为了解决数学上的一个基础性理论问题，并非是研制一台具体的计算机。科学发展史不断地告诉人们:许多重大的科学发明，往往是理论研究开路在先，工程技术实现在后。“万能图灵机”再一次令人们信服基础理论在科学发展道路上的决定性作用。图灵当年的纸上谈兵，那好似空中楼阁般的“万能图灵机”，实际上是现代计算机原理与计算机科学的开路先锋。
明白了图灵那无与伦比的贡献，人们就不难理解，何以冯•诺依曼对于“计算机之父”的桂冠坚辞不受。曾经担任过冯•诺依曼研究助手的美国物理学家弗兰克尔教授这样写道:“许多人都推举冯•诺依曼为'计算机之父'，然而我确信他本人从来不会促成这个错误。或许，他可以被恰当地称为'计算机的助产士'。依我之见，正是冯•诺依曼使世界认识了由图灵引入的计算机的基本概念。”弗兰克尔教授此言不虚，在1949年，冯•诺依曼发表了一篇题为《自动计算机的一般逻辑理论》的论文，客观而公正地阐述了图灵在计算机理论上的重大贡献。他写道:“大约12年前，英国逻辑学家图灵就开始研究'可计算问题'，他准确地给出了'自动计算机'的一般性定义。”冯•诺依曼宁愿把“计算机之父”的桂冠转戴在图灵头上。当然，这已经是在图灵离开普林斯顿十来年以后的事了，他当年在普林斯顿并没有像后来那样受人景仰。图灵曲高和寡，当年就能看明白他那篇文章划时代意义的，仅仅是少数杰出的数学家，如冯•诺依曼者。
客观地说，图灵、阿坦纳索夫、冯•诺依曼三人，都是计算机的先驱，计算机科学的奠基人，他们的伟大贡献被永远载入计算机的发展史中，若被称为“计算机之父”，他们都当之无愧。尤其是艾兰•图灵与冯•诺依曼，他们好似是计算机科学浩瀚星空中相互映照的两颗超级明亮的巨星。
4
1936年，阿兰•图灵提出了一种抽象的计算模型──图灵机(TuringMachine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
在纸上写上或擦除某个符号；
把注意力从纸的一个位置移动到另一个位置；
而在每个阶段，人要决定下一步的动作，依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：
一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依次被编号为0,1,2,...，纸带的右端可以无限伸展。
一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。
一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。
5
图灵机是图灵为了研究可计算问题而构思的一个理论装置，你只要想一想有限状态机就可以大概知道图灵机是个什么概念了，只不过图灵机的内存（纸带）是潜无穷的（也就是可以任意长啦，“潜无穷”是古稀蜡人的说辞）。图灵机的定义形象的说来就像老式的电传机：一个读写头，一根纸带（可能任意长），读写头不断读取纸带上的符号，并根据内在的状态转换规则转换当前状态，同时进行一些动作，譬如插除或改写当前字符，向前/向后移动读写头或保持不动等。至于其抽象的定义大抵就是有限状态机的定义了。
图灵机的这一定义现在我们看起来似乎是很显然的，然而当时却代表着一种思想上的革命，一种从无到有。图灵机实质上抽象出了我们平素进行机械式计算的核心规律，所以才等价于“一个人+纸笔+一定的规则”所进行的机械运算。
这么个理论机器首先就指明了创建计算机的可能性，然而这还不够，如果为了某一个问题就去创建一个特定的图灵机的话效率就太低了。图灵机理论的一个最美妙的结论就是存在“元图灵机（Universal Turing-Machine，直译应为一般图灵机/通用图灵机，然而“元图灵机”更精确地表达了其意思），所谓元图灵机其实就是把图灵机作为运算对象的图灵机，假设有一个元图灵机M，一个图灵机P以及P的输入数据D，那么将(P, D)喂给元图灵机M，M就能够吐出P(D)（即P在D上的结果）。而这便是现在我们所用的计算机的始祖模型，其中M就好比我们的计算机（元图灵机），P则是程序（编码后的图灵机），D则是程序P的输入数据。元图灵机的存在表明了我们可以用一台机器来解决所有图灵可计算（turing-computable）的问题——只要喂给它解决这个特定问题的图灵机编码（程序）以及问题的输入数据即可，该元图灵机就会模拟我们喂给它的那个图灵机P的行为，最终给出结果。元图灵机的存在性为计算机的诞生点燃了一盏明灯，这是图灵机理论中最漂亮的发现。