跳转到内容

计算理论

来自VeritasWiki 真理百科

计算理论(Theory of Computation)是计算机科学中研究"什么是可计算的""如何高效地计算"以及"哪些问题本质上无法由算法解决"的基础理论分支。它不关心某一台具体机器的工程实现,而是从最抽象的数学层面刻画计算的本质与边界。[1]计算理论的核心由两大部分构成:可计算性理论关注"哪些问题能够被算法求解",计算复杂性理论则关注"一个问题怎样才算被有效地求解"。

可计算性问题的提出

计算理论的起点是一个看似哲学的问题:什么是 computable(可计算)?20 世纪上半叶,数学家库尔特·哥德尔提出数学逻辑悖论,指出任何数学系统中总会存在不能被证明的命题,这促使人们思考"可计算"的精确含义。[2]1936 年,阿兰·图灵发表论文《论可计算数及其在判定问题上的应用》,提出"可计算性"理论,并尝试解答希尔伯特提出的判定问题。他从模拟人类思考过程和证明过程入手,提出用机器实现逻辑代码的执行,模拟人类各种计算和逻辑思维过程,由此奠定了此后一系列研究的理论基石。[3]图灵机本身不是一台真实的计算机,而是一个数学模型,它对"计算的本质"的认识,奠定了整个计算机科学的基础。

图灵机:计算的数学模型

图灵机是一台可以逐个处理一列符号的装置,也是对"计算"最经典的刻画之一。对图灵机的完整描述包括七个成分:有限的输入符号集、有限的内部符号集、特殊的空白符号、有限的状态集、状态变换规则、特定的初始状态以及一组终止状态。[4]它用一条可以双向无限延长的纸带作为存储,读写头在纸带上读取、写入并左右移动,根据当前状态与所读符号查表决定下一步动作。当且仅当存在一个图灵机,能把一个问题的每个实例作为输入并在有限变换后停止运行,这个问题才被称为"图灵机可计算"。图灵机被广泛应用于刻画计算机中的各种过程,从而成为理论计算机科学的核心概念。

不可判定与计算复杂性

在可计算性理论中,一个重要结论是并非所有问题都能被算法解决。停机问题就是最著名的例子:判断任意一个程序是否在有限时间内结束运行,这一判定问题在图灵机模型下是不可解的。[5]从可计算性等级看,所有语言的集合记为 All,能被图灵机枚举的语言集合记为 RE(递归可枚举语言),能被图灵机决定的语言集合记为 R(递归语言),三者构成严格的包含关系;证明的关键思想是"对角线法"。[6]与可计算性相对,计算复杂性理论考虑的是"一个问题怎样才能被有效解决",它研究时间与空间资源随问题规模增长的规律,把问题划分为易解与难解的不同类别。P 与 NP 问题正是复杂性理论中最核心、也最著名的未解难题之一。

丘奇-图灵论题与等价刻画

在图灵提出图灵机前后,还出现了若干关于"可计算"的等价刻画:哥德尔的递归函数、波斯特函数、丘奇的 λ 可定义函数等。令人惊奇的是,这些看似不同的刻画最终都被证明定义了同一类函数。[7]丘奇-图灵论题的非正式表述是:如果某个算法是可行的,那它同样可以被图灵机、以及另外两个理论所实现。由于这一假说依赖于"能够有效计算"这个模糊前提,它不具有数学定理一般的地位,也无法被严格证明,但几乎所有后来提出的计算模型(如寄存器机、波斯特系统、马尔可夫算法)都被证明在计算能力上与图灵机等价,这类系统被称为"图灵完全"。[8]今天,当我们说一门编程语言或一台抽象机器"图灵完备"时,指的就是它具备与图灵机同等的通用计算能力。

P 与 NP:一道悬了半个多世纪的题

可计算性划定了"能不能算",复杂性则追问"算得有多快",两条线索最终在 P/NP 问题上交汇。P 类是所有可以由确定型图灵机在多项式时间内解决的问题,NP 类则是所有能在多项式时间内验证其解是否正确的判定问题;1971 年,斯蒂芬·库克与列昂尼德·莱文相对独立地提出了 P 与 NP 是否相等的问题。[9]它被克雷数学研究所列入七个千禧年大奖难题,求解者可获 100 万美元奖金。2002 年一项面向 100 位研究者的调查中,61 人相信 P≠NP,9 人相信两者相等,22 人表示不确定,另有 8 人认为该问题可能与现有公理独立、因而无法证明或证否。[10]

分团问题常被用来说明这道题的形状:要在社交网络中找出 300 个彼此都是好友的人,验证一组候选人是否满足条件只需检查其间数万对关系,速度很快;但要从头"找"出这样一群人,目前没有人知道比遍历所有组合明显更快的办法。[11]这类"验证容易、求解未必容易"的问题构成 NP 完全类,只要其中任何一个找到多项式时间算法,所有 NP 问题都将随之可解。其现实意义直接而尖锐:现代密码学的安全性建立在"大整数分解很难"这一未经证明的假设之上,一旦 P=NP,现有加密体系的基础便会被动摇。[12]

计算理论的当代意义

计算理论虽然高度抽象,却与当代技术息息相关。一方面,它为现代计算机体系结构、编程语言设计和编译器理论提供了根本性的思想框架;另一方面,量子计算、超计算等前沿方向,也必须回到"什么是可计算""计算的物理极限何在"这类根本问题上接受检验。[13]丘奇-图灵论题对于心智哲学、物理学与超计算的可能性也都有深远的启示:宇宙是否是一台图灵机、是否存在不可计算的物理事件,至今仍是开放的研究议题。[14]正因如此,计算理论被称为"计算机科学的数学基石",它既是工程实践背后的哲学,也是划定机器能力边界的标尺。

参考资料