图灵机

图灵机就是假想的理想计算机，早期的计算机在实质上就是图灵机的具体实现。

图灵是一位英国数学家(1912—1954年)。只活了42岁，然而却在数学和计算理论方面做出了卓越的贡献。他在1937年发表的《关于可计算的数及其对判定问题的应用》一文中提出了一个非常重要的关于计算的数学模型，后世称之为图灵机。它的重要性在于，图灵对如何判断一类数学问题是否为机械可解作出理论回答。

在此文中，图灵从理论上证明，利用图灵机是将程序和数据以数码的形式存储于纸带上，即“存储程序”型的。这种程序能将高级语言写的程序译成机器语言程序。他解决了数理逻辑中的一个基本问题，即从理论上证明了通用数字计算机是可以制造出来的。各种各样的关于计算的数学模型，均以能被证明和图灵机等价作为它们具有最高计算能力的标志。图灵的论文发表不到10年，现实的电子计算机就问世了。计算机科学家也公认图灵的思想为电子计算机的诞生奠定了理论基础，图灵因此而获得了一项殊荣。目前国际上授予计算机科学家的最高学术成就奖就是以他的名字命名的。

图灵机的计算在一条带子上进行，这条带子在两个方向均为无穷长(可以把它想象成解析几何中的x轴)。带子上划分为无穷多个格(可以把它想象为x轴上长度为1的区间)。带子的上方有一个沿带子方向来回移动的读写头(读写头与带子的关系有点像录音机中磁头和磁带的关系)。计算通过读写头的移动和读写来完成。为了控制读写头的这些操作，每个图灵机有一个状态集{q_i}，其中包括一个开始状态和一个结束状态。它还有一组符号{S_i}，其中包括一个空白符号。另外它还有一个控制函数，该函数根据图灵机所处的当前状态和读写头所读到的当前符号决定图灵机的下一步操作，其中每一步操作包括三件事。第一，把某个符号写到读写头当前正“注视”的那个格上，以取代原来的符号;第二，读写头左移一格或右移一格或不移动;第三，用某一个状态取代当前的状态，使图灵机进入一个新状态。这个控制函数可以表为:(状态，符号)→(写符号，移动，状态)。顺序做完这3件事，图灵机的一个工作周期就结束。如果新状态不是结束状态，则可进入下一个工作周期。否则图灵机停机，计算任务宣告完成。所以结束状态也叫停机状态。图灵机停机以后，带子上的内容就是它的输出。

从英国政府在20世纪70年代透露出来的一些文件中可以得知，世界上第一台电子计算机不是1946年美国的莫希利等人制造的:ENIAC，而是英国于1943年造出的拥有1500个电子管的破译密码专用电子计算机COLOSSUS(巨人机)。这种机器的某些设计思想来自图灵，它的具体情况一直是保密的。1945年，图灵又提出了一个新的设计报告，这个设计中已有了“仿真系统”的思想，包括21个特点。但由于军事保密的原因，直到1972年，它才最终公诸于世，过去27年一直被保密。1947年，图灵有了人工智能的思想。在一份有关的报告中，他提出了自动程序设计的思想，这至今仍然是人工智能的重要课题。1950年，图灵提出了著名的“图灵测验”，从行为主义角度对智能问题给出定义:一个人在不接触对象的情况下，同对象进行一系列的问答，若他根据这些问答无法判断对象是人还是计算机，则可以认为这个计算机具有同人相当的智力。他预言20世纪末将会出现这种机器，但目前还没有能通过图灵测验的计算机。