五二小说网

手机浏览器扫描二维码访问

第五课 普林斯顿大学名人榜人工智能之父阿兰图灵（第3页）

可是，当时没有一台计算机有足够的运算能力去执行这个程序，他就模仿计算机，每走一步要用半小时。

他与一位同事下了一盘，结果程序输了。

后来美国新墨西哥州洛斯阿拉莫斯国家实验室的研究群根据图灵的理论，在MANIAC上设计出世界上第一个电脑程序的象棋。

可计算性理论与图灵机

在20世纪以前，人们普遍认为，所有的问题类都是有算法的，人们的计算研究就是找出算法来。

似乎正是为了证明一切科学命题，至少是一切数学命题存在算法，莱布尼茨（Leibniz）开创了数理逻辑的研究工作。

但是20世纪初，人们发现有许多问题已经过长期研究，仍然找不到算法，例如希尔伯特第10问题，半群的字的问题等。

于是人们开始怀疑，是否对这些问题来说，根本就不存在算法，即它们是不可计算的。

这种不存在性当然需要证明，这时人们才发现，无论对算法还是对可计算性，都没有精确的定义。

1934年，哥德尔（Godel）在埃尔布朗（Herbrand）的启示下提出了一般递归函数的概念，并指出：凡算法可计算函数都是一般递归函数，反之亦然。

1936年，克林（Kleene）又加以具体化。

因此，算法可计算函数的一般递归函数定义后来被称为埃尔布朗·哥德尔·克林定义。

同年，丘奇证明了他提出的λ可定义函数与一般递归函数是等价的，并提出算法可计算函数等同于一般递归函数或λ可定义函数，这就是著名的“丘奇论点”

，用一般递归函数虽给出了可计算函数的严格数学定义，但在具体的计算过程中，就某一步运算而言，选用什么初始函数和基本运算仍有不确定性。

为消除所有的不确定性，艾伦·麦席森·图灵在他的“论可计算数及其在判定问题中的应用”

一文中从一个全新的角度定义了可计算函数，他全面分析了人的计算过程，把计算归结为最简单、最基本、最确定的操作动作，从而用一种简单的方法来描述那种直观上具有机械性的基本计算程序，使任何机械的程序都可以归约为这些动作。

这种简单的方法是以一个抽象自动机概念为基础的，其结果是：算法可计算函数就是这种自动机能计算的函数。

这不仅给计算下了一个完全确定的定义，而且第一次把计算和自动机联系起来，对后世产生了巨大的影响，这种“自动机”

后来被人们称为“图灵机”

。

图灵在他的重要论文《论可计算数及其在判定问题上的应用》（1936年5月28日提交）里，对哥德尔1931年在证明和计算的限制的结果作了重新论述，他用现在叫作图灵机的简单形式装置代替了哥德尔的以通用算术为基础的形式语言。

由于速度很慢，尽管没有一台图灵机会有实际用途，图灵还是证明了这样的机器有能力解决任何可想象的数学难题，如果这些难题是用一种算法来表达。

现今，图灵机还是计算理论研究的中心课题。

他继续证明了判定问题是没有答案的。

他的证明首先展示了图灵机的停机问题（haltingproblem）是没有答案的，这是说不可能用一个算法来决定一台指定的图灵机是否会停机。

尽管他的证明比阿隆佐·丘奇在λ演算方面相等的证明晚发表了几个月，图灵的著作是更易于理解和直观的。

他的通用（图灵）机的概念也是新颖的。

这一通用机能够完成任何其他机器所能做的任务。

图灵机是一种自动机的数学模型，它是一条两端（或一端）无限延长的纸带，上面划成方格，每个方格中可以印上某字母表中的一个字母；又有一个读写头，它具有有限个内部状态.任何时刻读写头都注视着纸带上的某一个方格，并根据注视方格的内容以及读写头当时的内部状态而执行变换规则所规定的动作。

每个图灵机都有一组变换规则，它们具有下列三种形状之一：qiaRqi，qiaLqi，qiabqj意思是：当读写头处于状态qi时如果注视格的内容为字母a则读写头右移一格，或左移一格，或印下字母b（即把注视格的内容由a改成b.a，b可为so）。

艾伦·麦席森·图灵把可计算函数定义为图灵机可计算函数，1937年，阿兰·麦席森·图灵在他的“可计算性与λ可定义性”

一文中证明了图灵机可计算函数与λ可定义函数是等价的，从而拓广了丘奇论点，得出：算法可计算函数等同于一般递归函数或λ可定义函数或图灵机可计算函数。

这就是“丘奇-图灵论点”

，相当完善地解决了可计算函数的精确定义问题，对数理逻辑的发展起了巨大的推动作用。