图灵计算模型

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

哥德尔指出完备的形式化数学系统是不存在的,在此研究成果的影响下,20世纪30年代后期,图灵(A. M. Turing)从计算一个数的一般过程入手,对计算的本质进行了研究,从而开始了对计算本质的真正认识。

1935年,图灵开始对数理逻辑发生兴趣。数理逻辑又叫形式逻辑或符号逻辑,是逻辑学的一个重要分支。数理逻辑用数学方法,也就是用符号和公式、公理方法去研究人的思维过程、思维规律,其起源可追溯到17世纪德国的大数学家莱布尼兹,其目的是建立一种精确的、普遍的符号语言,并寻求一种推理演算,以便用演算去解决人如何推理的问题。在莱布尼兹的思想中,数理逻辑、数学和计算机三者均出于统一的目的,即人的思维过程的演算化、计算机化,以至在计算机上实现。但莱布尼兹的这些思想和概念还比较模糊,后续的许多数学家和逻辑学家沿着莱布尼兹的思路进行了大量实质性工作,使得数理逻辑逐步完善和发展起来,许多概念开始明朗起来。但是,“计算机”到底是怎样一种机器,应该由哪些部分组成,如何进行计算和工作,在图灵之前没有任何人清楚地说明过。

在听了剑桥大学组合拓扑学先驱纽曼(Maxwell H. A. Newman)教授的讲座之后,图灵进一步将兴趣明确为可判定问题,即能否至少从原理上证明,用确定的方法或步骤可以判断任何给定的数理命题。为了回答可判定问题,需要对“方法”加以定义,它不仅要精确,而且要令人信服。他分析了一个人能够完成哪些“机械的”步骤,估计了实现某些事物的思考应该有多大的规模,以及用理论机器如何表示这种分析。于是构想了“图灵机”模型。

简单来说,图灵机是一个逻辑机的通用模型。图灵机由一个控制器、一个读写头和一个无限长的存储带组成。处理器实际是有限状态控制器,能使读写头左移或右移,并对存储带进行修改或读出。于是通过有限指令序列就能实现各种演算过程。图灵机模型将可计算性这一概念与机械程序和形式系统的概念统一起来。

首先,可解性问题的讨论与算法的概念是分不开的。算法也称为能行方法或能行过程,是描述求解问题的方法和步骤,是对计算过程的精确描述,由一组明确定义且能机械执行的规则所组成。根据图灵的观点,他认为任一机械执行过程必须在一台机器上实现,通过引入机器状态,图灵机本质上具有指令特点的程序运算操作。

其次,根据图灵的研究,直观上讲,所谓计算就是计算者(人或机器)对一条两端可无限延长的纸带上的0和1执行操作,一步一步地改变纸带上的0或1的值,经过有限步骤最终得到一个满足预先要求的符号串的变换。他将此计算过程符号化为一个五元组,机器从给定的纸带上某起始点出发,其动作完全由初始状态及五元组来决定。图灵机是一种为可解问题设计的一种计算装置,它不是一台具体的现代意义上的计算机,但它却是一种操作十分简单且运算能力很强的计算装置,用其来计算所有可能想象到的可计算函数。

图灵机模型的实际意义在于:图灵证明,只有图灵机能解决的计算问题,实际计算机才能解决;如果图灵机不能解决的计算问题,则实际计算机也无法解决。即可计算性=图灵可计算性。因此,图灵机的能力概括了数字计算机的计算能力,对计算机的一般结构、可实现性和局限性产生了深远的影响。

图灵机与当时哥德尔、丘奇(A.Church)、波斯特(E. L. Post)等人提出的用于解决可计算问题的递归函数、λ演算和POST规范系统等计算模型在计算能力上是等价的。在这一事实的基础上,形成了著名的丘奇—图灵论题。

不过,图灵机等计算模型均是用来解决“能行计算”问题的,理论上的能行性隐含着计算模型的正确性,而实际实现中的能行性还包含时间与空间的有效性。伴随着电子学理论和技术的发展,在图灵机这个思想模型提出不到10年的时间里,世界上第一台电子计算机诞生了。