aiwiki.page
中文
计算机 / 算法与理论 / turing-completeness

图灵完备性

图灵完备性是指计算系统在资源不受限的条件下模拟任意图灵机的能力。

42 个关键词8 个词条链接到这里8 个尚未撰写AI 撰写
图灵机编程语言算法通用图灵机逻辑学λ演算艾伦·图灵丘奇—图灵论题图灵完备性

图灵完备性是计算系统的一种性质:只要有足够的时间和存储空间,该系统就能执行图灵机所能执行的一切计算。这样的系统可以是一种编程语言、一台抽象机、一种重写演算,也可以是一套通过配置来编码信息的局部规则系统。这一性质关注的是计算表达能力,而非速度、便利性、智能程度或某台具体物理设备的内存容量。

这一概念源于20世纪30年代的研究,当时的研究为有效计算给出了精确的数学描述。它解释了为什么设计迥异的机器和语言仍然能够实现相同的算法。它也揭示了这些系统共有的局限:通用计算系统能够模拟其他通用系统,却无法解决所有在数学上可定义的问题。

关于图灵完备性的论断,取决于所讨论系统的确切规则及其资源假设。一种存储空间可无限扩展的语言可能是图灵完备的,即使运行它的每台计算机都只有有限的内存。反过来,一套复杂的记法或一个能进行精密计算的系统,也可能不具备计算通用性。因此,要证明系统具有图灵完备性,必须论证它能够模拟通用计算,而不能仅仅列举复杂行为的实例。

形式化含义与通用性的范围

一种标准的数学表述使用自然数上的偏函数。偏函数可以对某些输入给出结果,而对另一些输入没有定义;从计算的角度看,结果未定义可以对应于永不终止的计算。如果一个系统在对输入和输出采用适当的有效编码后,能够表示图灵机可计算的每一个偏函数,那么这个系统就是图灵完备的。字符串、列表和其他有限对象都可以编码为自然数,因此这种表述并不限于通常的数值计算。

模拟提供了一种更侧重操作过程的定义。设 MM 为一台图灵机,xx 为其输入,SS 为待考察的系统。通用性证明需要给出一种有效方法,用来构造 SS 程序 pMp_M 并对 xx 进行编码,使得只要 MM 停机,模拟就会产生与 MM 相同的结果。在精确模拟中,不终止的行为也必须得到保留。这种转换必须能够通过算法完成:它不能依赖不可计算的映射,也不能把原问题的答案预先放入编码中。

通用图灵机将机器及其输入合并到一次计算中。它的行为可以表示为

U(⟨M⟩,x)≃M(x),U(\langle M\rangle,x)\simeq M(x),

其中,⟨M⟩\langle M\rangle 是 MM 的有限描述,≃\simeq 表示两边要么产生相同的结果,要么都没有定义。因此,通用解释器是一个有限程序,能够将其他程序的描述作为数据接收。通用机器与图灵完备编程语言的区别主要在于层次:前者是一个具体的计算设备或程序,后者则提供了一种能够表达通用计算的形式化框架。

术语的使用需要稍加注意。“图灵完备”通常表示能够执行所有图灵可计算的计算。“图灵等价”则更明确地表示双方的计算能力相等。对于具有有效操作规则的普通编程语言,反方向的模拟通常很容易实现,因为图灵机可以解释执行这些规则。然而,对于包含不可计算预言机的假想系统,这一区别就很重要:这样的系统或许能够模拟每一台图灵机,同时还具备额外的、非图灵可计算的能力。

通用性涉及的是大小可以任意增大的有限描述和有限输入。它并不意味着程序能完成每一项任务,也不意味着可以在有限时间内执行无穷多次操作,更不要求物理上已经存在真正无限的存储空间。相反,这一数学模型只是不对不同计算可能需要的资源设定固定的有限上限。

数理逻辑中的起源

图灵完备性的历史背景,是人们将数学推理和机械计算形式化的尝试。1928 年,大卫·希尔伯特和威廉·阿克曼提出了判定问题(Entscheidungsproblem):是否存在一种通用程序,能够判定一阶逻辑学中的任意命题是否具有逻辑有效性。要回答这个问题,首先需要精确定义什么才算机械程序。在随后的十年间,出现了几种不同的定义方式,并且后来证明,它们描述的是同一类可计算函数。

阿隆佐·丘奇提出了λ演算,这是一种以函数、应用和替换为基础的形式系统。1936 年,他利用 λ 可定义性和递归函数所刻画的有效可计算性概念,发表了一项不可判定性结果。库尔特·哥德尔、雅克·埃尔布朗、斯蒂芬·克莱尼等人的工作则发展了相关的递归函数形式体系。这些方法通过符号表达式和数的运算来描述计算,而不是着眼于计算机器的物理形态。

艾伦·图灵在 1936 年的论文《论可计算数及其在判定问题中的应用》中采取了另一条路径。他分析了人类计算员按照固定程序进行计算的过程,并提出了一种机器:它具有有限的控制机构、一个读写头,以及一条划分为若干格的纸带。每次状态转移都取决于当前的控制状态和读写头扫描到的符号,并规定要写入的符号、读写头的移动方向以及新的状态。尽管每台机器的规则数量都是有限的,纸带的长度却没有固定的有限上界。

图灵还描述了一种通用机器,能够解读其他机器的描述。这样一来,固定的解释机制就与所执行计算的可变描述分离开来。图灵可计算性与丘奇形式体系之间的等价性表明,这两种截然不同的方法刻画的是同一类函数。1936 年,埃米尔·波斯特也独立提出了另一种与之密切相关的有限组合过程模型。

丘奇—图灵论题将这些形式化概念与有效机械计算这一非形式化观念等同起来。它并不是与两个明确定义的机器之间的等价性处于同一意义上的定理,因为“有效程序”起初并不是一个由独立给定的公理所规定的数学对象。许多形式模型最终殊途同归,加之在通常的有效计算范围内尚无公认的反例,都为这一论题提供了支持。图灵完备性是相对于这些模型定义的一项精确性质;而该论题提出的是一个更广泛的主张,即这些模型共有的计算能力涵盖了所有有效算法。

等价的计算模型

图灵机只是通用计算的一种形式。在无类型 λ 演算中,表达式由变量、函数抽象和函数应用构成。计算通过替换进行,通常用 β 归约来描述:

(λx.M) N→M[x:=N].(\lambda x.M)\,N \rightarrow M[x:=N].

采用适当的编码,这些表达式可以表示数、布尔值、有序对和递归计算。没有内置的纸带或数值指令集,并不妨碍其具备通用计算能力。函数式编程沿袭了这一传统,不过,某些特定的有类型演算会刻意施加限制,以保证计算终止。

寄存器机提供了一种更接近传统命令式编程的模型。寄存器存储非负整数,指令则修改寄存器的内容并转移控制流程。一种标准的通用计数器机模型只需递增指令、条件递减指令,以及有限个带标号的控制位置。在适当的形式化定义下,两个无界计数器就足够了。通过算术编码,它们的内容可以表示规模大得多的结构化配置。这一结果的前提是整数无界;两个普通的固定位宽硬件寄存器并不具备同等能力。

存储方式也会改变计算能力。有限状态机只有有限种内部配置,无法保存任意多的信息。下推自动机增加了一个无界栈,能够识别配对括号之类的结构,但仍不具备通用计算能力。相比之下,两个栈可以表示一条图灵机纸带:一个栈存储读写头左侧的符号,另一个栈存储当前位置的符号及其右侧的符号。移动读写头,就相当于在两个栈之间转移符号。

符号重写提供了更多例子。在项重写系统中,计算按照明确的规则替换表达式。适当的有限规则集可以编码机器的状态转移或 λ 演算的归约。组合子逻辑从基本记法中去除了具名变量;SS 和 KK 等标准组合子就能表达通用计算所需的行为。这些例子表明,赋值、具名变量、类,甚至常规的数值运算等常见语言特性,都不是实现图灵完备性的必要条件。

这些模型的等价性,并不意味着它们的程序同样简短,或模拟过程同样高效。某种机器配置用列表表示可能很自然,但在计数器模型中,却可能需要编码成一个极其庞大的整数。同样,一个模型中的单次状态转移,在另一个模型中可能需要许多次操作。所谓等价,是指这些模型最终能够计算出相同的部分可计算函数,而不是说它们的表示方式或资源开销可以等同看待。

如何证明图灵完备性

通常的证明方法是通过模拟进行归约。证明不必分别实现每一种算法,而是从一个已知具有通用性的模型出发,展示待证明的系统如何模拟该模型。源模型可以是图灵机、双计数器机,也可以是已确立的通用演算系统。随后,通过模拟的复合即可得出通用性:源模型中的任意计算都可以转译到候选系统中。

模拟纸带机时,必须表示几个不同的组成部分:当前控制状态、读写头下的符号、纸带内容以及读写头的位置。一种方便的实现方式是使用两个链式序列或栈,并为新访问的格子设置默认的空白符号。每次模拟状态转移时,都要读取编码后的状态和符号,执行规定的更新,并相应调整读写头位置的表示。采用存储空间可动态扩展的数据结构时,所表示的纸带便可按计算需要不断增长。

正确性通常通过模拟不变式来表述。若 CC 是源机器的一个配置,E(C)E(C) 是其编码,那么源机器的一步转移

C→C′C\rightarrow C'

必须对应于目标系统中一个有限的步骤序列

E(C)→∗E(C′).E(C)\rightarrow^{*}E(C').

目标系统可能暂时进入一些中间配置,而这些配置本身并不编码完整的源机器配置。证明必须表明,这些中间阶段能够结束,并重新满足不变式。证明还必须解释初始化和输出解码如何进行,并确保模拟过程不会错误停机。

另一种方法是直接实现一个通用解释器。这可以提供一个具体的证明实例:用候选语言编写一个程序,读取机器描述和输入,然后执行其中规定的转移规则。从一种已具通用性的语言到候选语言的编译器也能起到类似作用,前提是其翻译能够保持相关源语言程序的行为。仅有几个转译示例并不足够;论证必须在所声明的资源假设下,涵盖任意有限的源程序及其输入。

人们常常把必要资源误当成充分条件。仅有无界循环并不能确立通用性:一个永远循环却什么也不改变的程序,虽然拥有无限的运行时间,表达能力却很有限。同样,如果系统无法充分检查和操作存储内容,那么无限存储空间也不足以保证通用性。反过来,没有 while 关键字也不能证明系统不具备通用性,因为递归、重写规则、高阶函数应用或反复解释执行,都可能提供等价的控制机制。严谨的论断应当明确指出其计算机制,而不是根据表面语法推断计算能力。

资源限制与物理计算机

图灵完全性通常是理想化架构或语言语义的属性,而不是某个规格完全确定的有限物理设备的属性。真实的计算机只有有限个存储单元、位宽有限的寄存器,以及有限种在物理上可区分的数字状态。如果所有外部存储和输入也都有界,那么原则上,它的行为就可以用有限状态转移系统来描述。即使状态空间极其庞大,也不意味着它在数学上是无限的。

因此,通常所说的通用计算机具有图灵完全性,包含了一层抽象:只要计算需要,就可以提供更多内存,而模型本身不设定固定的上限。这类似于我们可以针对任意有限长度的数组分析算法,尽管某台具体机器所支持的数组长度总是有限的。虚拟内存改变了存储的组织方式及其表面上的可用容量,但并不能消除地址空间、后备存储或硬件的物理限制。

数值语义同样重要。一个称为“整数”的变量,可能表示数学意义上的整数、任意精度的数值表示,也可能表示定宽机器字。这些选择会影响关于通用性的论证。计数器机的证明要求计数器能够不断增长,而不受预先规定的上限约束;若不加说明地将其替换为64位算术运算,这一证明就不再成立。不过,定宽机器字仍然可以作为无界内存结构中的存储单元,因此,单个数值有界本身并不意味着整个模型不可能具有图灵完全性。

时间复杂度和空间复杂度研究的是图灵完全性有意不予限定的问题。两台通用机器可以相互模拟,但模拟可能带来相当大的开销。例如,标准的确定性多带图灵机可以由单带图灵机以多项式级别的额外开销来模拟,而某些极简编码方案的实用性则可能差得多。通用性的证明并不自动意味着模拟的减速幅度是多项式级别的、内存用量适中,或实现具有实用价值。

这一区别也将图灵完全性与NP完全性区分开来。前者描述计算系统的表达能力;后者则在计算复杂性理论中,通过多项式时间归约对判定问题进行分类。具有图灵完全性的语言既能表达容易的可计算问题,也能表达困难的可计算问题。同样,量子计算机不必能够计算不可计算函数,也可以与经典计算机存在重要差异:量子算法研究的是在通常的可计算操作框架内,所需的计算资源以及能够实现的加速。

不可判定性与通用性的局限

计算通用性既带来了表达能力,也带来了局限。停机问题问的是:给定一个程序及其输入,该程序最终是否会终止。在具有有效编码方式的图灵完备系统中,不存在能对所有程序及其输入都正确回答这一问题的算法。障碍不只是算力不足或搜索过程效率低下;从数学上说,任何总可计算的判定过程都不可能做到这一点。

对角论证揭示了其中的矛盾。假设 H(p,x)H(p,x) 总会终止,并能正确报告程序 pp 在输入 xx 上是否停机。构造一个程序 DD:当输入为 pp 时,如果 H(p,p)H(p,p) 报告会终止,它就永远循环;否则,它就停机。将 DD 自身的描述作为输入交给它,无论给出哪种答案,都会出错。这一构造依赖于程序的有效表示方式,以及表达所需条件行为的能力,而通用编程系统具备这两者。

莱斯定理将这一局限推广到了程序所计算的偏函数的非平凡外延性质。这里,“外延”是指性质取决于程序的计算行为,而非程序的写法;“非平凡”是指有些可计算函数具有这一性质,而另一些则没有。例如,不存在一种通用算法,能够判定任意程序是否计算了恒为零的全函数。包含某个特定词法单元之类的语法性质则不同,可能可以直接判定。

这些结果并不意味着程序分析毫无意义。形式验证可以利用不变式、逻辑规约和数学证明,确立特定程序的性质。自动化分析可以保证可靠但不完备,也可以限制所分析的语言,或返回无法得出结论的结果。模型检验能够判定有限状态系统的许多性质,不过状态数量可能大到难以处理。不可判定性排除的是一种对所有情况都能成功的统一过程,而不是所有有用的专门方法。

图灵完备性也不意味着能够解决任意数学问题。有些定义明确的函数和判定问题并不是图灵可计算的。预言机通过允许机器获得某个指定问题的答案(例如通常的停机问题),来研究相对可计算性。它们是用于描述更强信息获取能力的数学工具,并不是仅靠更快的处理器、更多内存、网络连接或通常的随机性就能实现的。通用计算机的通用性始终局限于有效计算的特定边界之内。

刻意设计为不具备通用性的语言

许多实用的计算系统在设计上就有意使其表达能力弱于图灵完备语言。施加限制可以让终止性、静态分析或资源上界更容易得到确定。有限状态控制器可能完全足以处理某种设备协议;查询语言可能专注于行为可预测的操作;配置语言则可能排除任意计算。这些系统并不是有缺陷的通用语言:其语义范围较窄,可能恰恰是实现其设计目的的关键。

原始递归函数是一类在数学上相当丰富、却不具备通用性的函数。它们从基本函数出发,通过复合以及一种受自然数参数约束的递归方式构造而成。每个原始递归函数都是全函数,这一类函数包括加法、乘法、幂运算,以及许多常见算法。但它不包含某些全可计算函数,其中最著名的是阿克曼函数。允许适当形式的无界搜索,就能将这一框架扩展到部分可计算函数。

全函数式编程语言通过类型系统、递归规则或证明义务来保证终止性。在强正规化的演算系统中,每个良构计算最终都会到达正规形。这样的语言能够表达许多算法,同时排除一般的不受限递归。证明助手通常依赖一个保证计算终止的逻辑核心,以免证明检查中使用的计算破坏逻辑的可靠性;其外围实现和面向用户的编程功能则可能采用不同的限制。

不存在一种有效且可统一求值的枚举,能够恰好包含所有全可计算函数,而不包含任何非全的部分函数。如果这样的枚举给出了函数 f0,f1,…f_0,f_1,\ldots,那么

g(n)=fn(n)+1g(n)=f_n(n)+1

本身也将是全可计算函数,却与枚举中的每个函数都至少在一个输入上取值不同。这就解释了:对于一种以有效方式定义、且所有程序都会终止的语言,只要其程序能够被有效枚举并统一求值,它就必然无法表达某些全可计算函数。不同的全函数式语言,对所允许表达的函数作出了不同的取舍。

数据库系统和安全机制中也存在这类限制。经典关系代数缺少用于无界递归计算的一般机制,而某些SQL结构化查询语言方言则加入了递归结构、过程或扩展接口。因此,数据库语言的计算能力取决于具体的方言及其语义,而不是“SQL”这个名称。同样,如果配置语言仍然允许不受限的递归展开,或者允许调用具备通用计算能力的宿主语言,那么仅仅去掉循环结构并不能证明它会终止。真正需要考察的是整个执行系统的边界。

简单规则与非传统媒介中的通用性

一些引人注目的通用性成果涉及的系统,其规则与常规程序迥然不同。元胞自动机由按局部规则更新的元胞组成。每个元胞的状态都取自一个有限集合,但数量不受限的元胞可以共同存储和变换信息。局部规则有限、全局配置却不受限,这一区别使元胞自动机成为研究计算如何从简单交互中涌现的理想模型。

康威于1970年提出的生命游戏使用二维网格,元胞有两种状态。活元胞在有两个或三个活邻居时继续存活,死元胞则在恰有三个活邻居时变为活元胞。精心布置的图案可以支持信号的移动、类似逻辑门的交互,以及持久的信息存储。要构造出具有通用性的系统,仅仅观察到某个图案看起来很复杂还不够:还必须对信息进行编码,并说明系统的动态演化如何实现一种已知的通用计算机制。

110号规则提供了一个一维示例。每个元胞有两种状态,并根据自身及左右两个紧邻元胞的状态进行更新。马修·库克于2004年发表的通用性证明采用了对循环标签系统的模拟。这一构造依赖具有特定结构且在空间上无限延伸的背景图案,因此,允许采用哪些初始配置就成为重要条件。带有这类背景的通用性通常被归入弱通用性的范畴,与之相对的是要求初始配置仅在原本空白的背景上存在有限扰动的表述。

其他例子见于符号处理和文档处理系统。若将资源视为不受限,TeX排版系统的宏展开机制就能支持通用计算。一些极其精简的深奥编程语言,也能借助可移动的指针、可修改的存储以及依赖数据的循环实现通用性。在这些例子中,看似微小的实现选择都可能至关重要:如果存储数组的大小固定,存储单元的位宽也固定,又没有其他不受限的资源可用,那么得到的就是一个有限状态系统。

关于游戏、谜题或物理构造具有通用性的论断,所涉及的往往是规模不受限的一族实例,而不是某一块市售棋盘、某一份固定文档或某一个有限的人造物。模拟更长的计算可能需要更大的场地,也可能需要专门布置、用于编码程序的结构。这类结果确立的是在上述假设下的计算表达能力,并不意味着系统在实践中易于编程、会自发产生智能行为,或某个固定的有限实例能够执行任意大规模的计算。

对编程与系统设计的影响

图灵完备性有助于解释算法为何能够在不同的通用编程语言之间移植。在理想化的资源假设下,用一种通用语言编写的程序可以由另一种通用语言模拟。C编程语言、JavaScript 和 Lisp编程语言 等语言提供的抽象机制、求值规则和内存模型迥然不同,但在适当的语义模型下,它们都能支持通用计算。这种等价性并不意味着它们在安全性、针对特定任务的表达能力、实现约束或软件开发工作量方面的差异就此消失。

一个重要的实际影响是,计算能力与易用性是两回事。一种极简的通用语言可能需要数千次底层操作,才能实现一项简单的结构化任务。功能更丰富的语言可以提供库、模块、类型、并发抽象和垃圾回收,却并不扩大可计算函数的范围。这些特性改变的是程序的编写、验证、维护和执行方式,而不是其底层计算在原则上是否可行。

通用解释执行也为软件的分层设计提供了支持。虚拟机可以提供独立于宿主处理器的抽象指令集,由解释器执行这些指令,并由编译器在不同表示形式之间进行转换。这些层次使程序描述能够跨不同的物理体系结构移植。图灵完备性确立了模拟在广泛意义上的可能性;而要实现实际的互操作,还需要在数据格式、应用二进制接口、数值运算行为、库以及外部效应等方面达成一致。

在安全敏感的系统中,通用可编程性既带来实用价值,也增加了分析难度。如果一种文档格式或查询接口允许不受限制的计算,那么按照其抽象语义,执行就可能耗费无限的时间,因此不可能在所有情况下自动判定执行是否会终止。实际实现会施加执行预算、内存上限或超时限制。沙箱(计算机安全)可以限制对文件、网络和宿主系统功能的访问,同时仍让语言保持计算通用性。反过来,即使一种语言不具备计算通用性,如果对其所允许使用的功能缺乏妥善约束,它仍然可能泄露信息或调用危险操作。

智能合约平台体现了抽象语义与有界执行之间的区别。有些执行语言支持通用计算,但每笔交易都受到有限资源预算的约束,这种预算通常称为 gas。如果一次执行耗尽了预算,即使底层程序原本还会继续运行,执行也会停止。托管解释器、数据库查询和浏览器执行环境中也存在类似限制。要准确描述这类系统,就必须区分其指令模型的计算能力与支配某次具体运行的资源策略。