图灵机

来自计算思维百科
跳转至: 导航搜索

图灵机,又称图灵计算、图灵计算机,是由数学家阿兰·麦席森·图灵(1912~1954)提出的一种抽象计算模型,即将人们使用纸笔进行数学运算的过程进行抽象,由一个虚拟的机器替代人们进行数学运算。

基本概念

1936年,英国科学家阿兰·图灵(Alan Turing,1912-1954年)发表的“论可计算数及其在判定问题中的应用”一文中,就此问题进行了探索。这篇论文被誉为现代计算机原理开山之作,他提出了一种十分简单但运算能力很强的理想计算装置,并描述了一种假想的可实现通用计算的机器,这就是计算机史上著名的“图灵机”。

模型

直观地看,图灵机是由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成,如图1所示:

8.3.2.png


图1 图灵机

图灵机的带子被划分为一系列均匀的方格,读写头可以沿带子方向左右移动,并可以在每个方格上进行读写。

写在带子上的符号是一个有穷字母表:{S0,S1,S2,…,Sp}。通常,可以认为这个有穷字母表仅有S0、S1两个字符,其中S0可以看作是0,S1看作是1,它们只是形式化的两个符号。机器的控制状态表为:{q1,q2,…,qm}。通常,将一个图灵机的初始状态设为q1,同时还需要确定一个具体的结束状态为qw

一个给定机器的程序认为是机器内的五元组(qiSjSkR(或L、N)ql)形式的指令集,五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作,五个元素的含义如下:

①qi表示机器当前所处的状态;

②Sj表示机器从方格中读入的符号;

③Sk表示机器用来代替Sj写入方格中的符号

④R、L、N分别表示向右移一格、向左移一格、不移动;

⑤q1表示下一步机器的状态。

工作原理

机器从给定带子上的某起始点出发,它的动作完全由其初始状态及机内五元组来决定。一个机器计算的结果是从机器停止时带子上的信息得到的。容易看出,q1S2S2Rq3指令和q3S3S3Lq1指令如果同时出现在机器中,当机器处于状态q1,第一条指令读入的是S2,第二条指令读入的是S3,那么机器会在两个方块之间无休止地工作。另外,如果q3S2S2Rq4指令和q3S2S4Lq6指令同时出现在机器中,当机器处于状态q3并在带子上扫描到符号S2时,就产生了二义性的问题,机器就无法判定。

例如:设b表示空格,q1表示机器的初始状态,q4表示机器的结束状态。如果带子上的输入信息为10100010,读写头对准最右边第一个为0的方格,状态为初始状态q1。按照以下规则执行后,输出正确的计算结果。

计算规则如下:

q101Lq2

q110Lq3

q1bbNq4

q200Lq2

q211Lq2

q2bbNq4

q301Lq2

q310Lq3

q3bbNq4

计算过程如下:

8.3.3.png

显然,最后的结果是10100011,即对给定的数加1。其实,以上命令计算的是这样一个函数:S(x)x+1。

图灵机不仅可以计算后继函数S(x)x+1,显然还可以计算零函数N(x)=0,投影函数Ui(n)(x1',x2',…,xn)=xi,(1≤i≤n)以及这三个函数的任意组合。这三个函数都属于初始递归函数,而任何原始递归函数都是从这三个初始递归函数经有限次的复合、递归和极小化操作得到。因此,每一个原始递归函数都是图灵机可计算的。

意义

尽管图灵机具有可模拟现代计算机的计算能力,并且蕴含了现代存储程序的思想。但是在实际计算机的研制中,还需要有具体的实现方法和实现技术。在图灵机提出后不到十年,世界上第一台存储程序式通用数字电子计算机就诞生了。由于阿兰·图灵对计算机科学的杰出贡献,美国计算机协会(ACM)决定设立“图灵奖”,从1966年开始颁发给在计算机科学技术领域做出杰出贡献的科学家。

阿兰·图灵对现代计算机的主要贡献有两个:一是建立图灵机理论模型;二是提出定义机器智能的图灵测试。