图灵（Alan Turing）的伟大贡献

-- 纪念图灵诞辰100周年（4,5,6）

西北大学  郝克刚

图灵机是为直观的“计算”给出一个严格的形式化的定义。它的神妙之处还在于它的组成和执行规则相当简单，但是功能却非常强大。试图对其扩展来扩大它的计算能力都不成功。例如多增加几个无穷长的带子和读头，最后证明它的计算能力还是等价于原来的图灵机。即使是非确定的图灵机的能力也等价于确定的图灵机。

图灵 1937年被邀请到美国普林斯顿和丘奇(Alonzo Church)一起合作，他们提出了一个后来被叫做丘奇- 图灵论题。这个论题断言图灵机同直观的有效的函数计算具有等价的问题求解机制。即所有“能解”的问题都存在一个图灵机，只要把问题放在图灵机带子上，若有解则停机后带子内容即是解答。这个断言叫做“论题”是由于他无法严格证明。

那个时代和后来曾经提出过不少的形式化计算模型，如λ演算、递归函数、正规算法、POST系统、递归算法（胡世华）等，全都被证明同图灵机等价。这些事实在一定程度上加强了这个论题。

当然在学界也有一些对此论题的质疑，例如有人认为交互式机器超越了图灵机（Peter Wegner），有人认为量子计算机，生物计算机可能会超越图灵机，但是这些意见都还没有能给出具有说服力的论证，从而也没有为普遍学者所认可。在纪念图灵诞辰100周年之际，关于是否有超越图灵机计算能力的模型也是一个争论的热门话题。

5） 使不可解问题的证明成为可能

由于图灵机是为 “计算”给出的一个严格的形式化的定义。从而使严格证明某些问题是“不可计算”（“不可解”或“不可判定”）成为可能。要知道这种否定的证明通常是相当困难的，所以说这也是图灵的一个重要贡献。

首先可以证明图灵机的停机问题是不可判定的。接着证明了推导系统的字的问题是不可判定的。后来又证明了逻辑系统以外的许多实际数学问题是不可判定的。如有名的希尔伯特第十问题是不可解的，即不存在这样的算法，它能判定一个任意的丢番图方程(Diophantine Equation)是否有整数解。

即使是不可解的问题，也有程度层次的不同，克林(Stephen Kleene)曾对其进行了分层。笔者早期也曾涉及此类研究，提出过“可构造实数论中若干谓词在Kleen分层下所属的类型”（《数学学报》1964年第四期。）

6） 为计算机科学的研究奠定重要的理论基础

图灵机的提出，影响深远，可以说它为以后整个计算机科学的研究奠定了重要的理论基础。例如关于的形式语言和自动机的理论研究就以图灵机作为基础，它对计算机编译系统和操作系统技术的发展起着重要作用。

乔姆斯基（Avram Noam Chomsky）曾按生成文法的不同对语言进行分类。所谓语言就是某字母表上字的集合。而后来发现语言又和接受它的机器类型有关。说某机器M 接受某个字 w ，是指如果以字w 作为机器 M 的输入（对图灵机来说就是作为他的初始字），运行后以某指定的接受状态结束计算。也就是说，如果 M 在其他状态结束计算，或计算不终止，则M不接受该字 w 。

理论研究证明语言，生成文法和机器的类型有如下的对应关系：

再例如关于算法复杂度的研究，也常以图灵机作为研究的起始模型。我们知道，同样是算法，在机器上运行时所需要的时间和空间资源的数量时常相差很大。因而需要定义算法的复杂度来作为度量算法优劣的一个重要指标。假定算法在图灵机上计算的输入字的长度是l，那么完成此计算所需要的最长时间（即运算的最长步数）是l的一个函数，称此函数为此算法的时间复杂度。同样，完成此计算所需要的最大空间（即运算涉及的格子最大数量）也是l的一个函数，称此函数为此算法的空间复杂度。例如函数不超过多项式函数，就说此算法具有多项式时间或多项式空间复杂度。函数不超过指数函数，就说此算法具有指数时间或指数空间复杂度。

大家知道指数函数要比多项式函数增长得快得多，因而常认为具有多项式时间复杂度的算法是 “实际可行的 (feasible) ” 算法。而具有指数时间复杂度的算法是实际不可行的。

例如：多项式函数t=n³, n=60, t=216000，一台百万次计算机，0.2秒即可完成。而指数函数。t=3ⁿ, n=60, t=3⁶⁰~4x10²⁸，若能用10亿台百万次计算机并行运算，需要运行一百万年。

这里再顺便介绍一下悬赏奖金一百万美元巨奖，被称为“千僖年数学难题”之一的“P = NP?”问题。这个问题是：“在多项式时间界限下，确定的和非确定的图灵机器是否具有同等的功能？”

我们知道，确定的和非确定的有穷自动机的功能是相同的，它们所接受的语言都是正则集合。如果不加多项式时间的限制，确定的和非确定的图灵机的功能也是相同的，它们所接受的语言都是递归可枚举集。如果对图灵机加上空间的限制，在多项式空间界限下，确定的和非确定的图灵机也具有同样的功能。但是，并不是在所有情况下确定的和非确定的机器都具有同样的功能。例如，对具有一个下推存贮的有穷机器来讲两者的功能是不相同的，非确定性的下推自动机所接受的语言是上下文无关语言，而确定的下推自动机所接受的语言却是上下文无关语言的一个真正的子类。

那么在多项式时间界限下，确定的和非确定的图灵机器是否具有同等的功能呢？即是否P = NP? 回答究竟是肯定还是否定，只能有一种。这个问题的提法相当清晰，但是要解答这个问题却不容易。当代很多有名的计算机科学家都研究过这个问题，问题至今仍未解决，而且愈来愈觉得是相当困难的。解决这个问题似乎需要在方法上有重大突破。

上世纪70年代提出的NP完全的理论，对解决此问题有很大的推进，但仍未最终解决。笔者30年前曾写过一篇综述文章，"NP完全问题及有关理论研究"（《计算机科学》，1980年1期。）

不久前，有一位HP公司的工程师宣称他证明了P != NP，不过目前还尚未被认可。

                                                （未完待续）