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

通用图灵机

通用图灵机是一种抽象计算机器,能根据编码后的机器描述及输入,模拟任意图灵机。

29 个关键词8 个词条链接到这里3 个尚未撰写AI 撰写
图灵机艾伦·图灵算法计算机判定问题λ演算可计算性理论编程语言通用图灵机

通用图灵机是一种图灵机,只要获得另一台图灵机的适当描述及其输入,就能模拟那台机器。它自身的转移规则保持不变:不同的计算是通过改变最初写在纸带上的信息来实现的,而不必为每项任务另造一台机器。艾伦·图灵在其1936年的论文《论可计算数及其在判定问题中的应用》中提出了通用图灵机,为通用计算确立了精确的数学形式。

通用性将算法理论与可编程计算机的组织方式联系起来。机器的描述可以表示为数据,由另一台机器读取,并用于决定后者的行为。这一原理是解释器和多种软件模拟方式的基础,不过,通用图灵机是一种抽象的数学对象,而不是某种具体电子计算机的设计蓝图。它的意义还涉及计算的极限:由于程序可以被表示和模拟,我们便能够证明,关于程序行为的某些问题无法由任何算法判定。

历史起源与图灵的构造

图灵在研究与大卫·希尔伯特数理逻辑纲领相关的判定问题时,提出了他的机器模型。这里所涉及的判定问题,是要寻找一种有效过程,用以判定任意给定的一阶逻辑公式是否逻辑有效。要回答这个问题,就必须足够精确地说明有效过程能够做什么。图灵从遵循明确规则进行计算的人入手,分析其基本操作:查看符号、修改符号、转移注意位置,以及按照有限的一组指令继续操作。

伦敦数学会于1936年5月收到图灵的论文,并在1936—1937年的出版周期内将其刊登于学会会刊。论文描述的机器配有一条划分为方格的纸带、一个能够查看和修改方格内容的读写头,以及有限个内部状态。尽管纸带可以无限延伸,支配任何一台特定机器的规则却是有限的。这一区分使图灵得以将计算最终可能需要的、不受限制的工作空间,与定义该计算的有限指令分开。

在这一框架中,通用机是一台能够解释其他机器描述的机器。图灵为机器指令引入了“标准描述”,并给出了这种描述的数值表示。通用机可以读取这种表示,复现其中所描述的计算。他最初的论述着重于产生符号序列的机器,尤其是产生可计算数各位数字的机器,而非现代惯例中接收有限输入并返回有限输出的程序。这两种表述可以通过有效编码相互联系,但所用术语和停机约定有所不同。

同一时期,阿隆佐·丘奇利用λ演算证明了一项不可判定性结果。图灵的工作提供了另一种形式体系,并对逐步进行的机械计算作出了格外直观的分析。这些方法得出了相互一致的结论,有助于奠定可计算性理论的基础。通用机的构造尤其重要,因为它表明,各种计算过程虽然看起来千差万别,却并不需要种类同样繁多的基本计算设备。

图灵的贡献应与后来存储程序计算机的工程发展史区分开来。可编程设备早有先例,而电子计算技术则是在多个项目和机构的推动下发展起来的。1936年的构造从数学上证明,一台固定的机器能够复现某个精确定义的机器类别中所有机器的行为。电子元件、实用存储器、指令时序和输入输出设备等问题,则属于后续发展阶段的范畴。

形式定义与计算行为

一种常见的现代定义用如下元组表示确定性图灵机:

M=(Q,Σ,Γ,δ,q0,qacc,qrej).M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}}).

其中,QQ 是有限状态集,Σ\Sigma 是输入字母表,Γ\Gamma 是包含 Σ\Sigma 和空白符号的纸带字母表。转移函数 δ\delta 规定机器读取一个纸带单元后,如何改变状态、写入符号并移动读写头。其余分量分别指定初始状态、接受状态和拒绝状态。其他约定可能采用单一停机状态、部分转移函数、多条纸带,或允许读写头以不同方式移动。

设 ⟨M⟩\langle M\rangle 是 MM 的一种有效编码,⟨M,x⟩\langle M,x\rangle 则是由该描述与输入串 xx 组成的有序对的编码。如果机器 UU 对每一个 MM 和 xx,都能重现 MM 在 xx 上的指定计算行为,就称 UU 具有通用性。若将机器理解为计算部分函数的装置,这通常表示为:

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

符号 ≃\simeq 表示部分计算相等:如果右侧计算停机并得到一个值,左侧计算也会停机并得到对应的值;如果右侧计算不停机,左侧的模拟也不会停机。输出格式可能需要采用固定的解码约定。

这一定义并不要求模拟器的实际状态与被模拟机器的状态一致。MM 的一次转移可能对应 UU 的多次转移,而被模拟的一个纸带符号也可能占据通用机纸带上的多个单元。关键在于,所表示的格局与所模拟的转移之间必须具有正确的对应关系。格局记录当前状态、纸带内容和读写头位置,包含确定下一步操作所需的信息。

通用性针对的是所选模型中的所有机器,而不只是一大批实用程序。其中的量词至关重要:同一个固定的 UU 必须能够处理每一个有限的机器描述和每一个允许的输入。不能针对每一台被模拟机器,分别替换或扩充它的有限控制器。相比之下,其纸带上的描述可以任意长,只要在每次具体计算中是有限的即可。

如何处理格式不合法的描述,通常只是次要的约定。通用机可以拒绝这些描述,也可以停机并报告指定错误,或以其他规定的方式处理。模拟要求只适用于有效编码。同样,通用性也不要求机器对每个输入都给出结果。由于某些被模拟的计算会永远运行下去,忠实的通用模拟器也必须能够永远运行下去。因此,通用计算自然是一种关于部分可计算函数的理论,而不只是关于处处有定义的函数的理论。

程序编码与模拟执行

构造通用机的第一个要素,是以可计算的方式表示指令。一次转移可以用一条有限长度的记录来描述,其中包含原状态、读到的符号、要写入的符号、移动方向以及新状态。状态和符号都可以编号,而编号可以写成二进制串,也可以采用其他有限编码。通过分隔符、长度字段或自定界约定,可以确保生成的序列没有歧义。这样,即使被模拟的机器使用许多不同的状态和符号,其机器描述仍然只是固定字母表上的一个普通字符串。

模拟器还需要表示被模拟机器的格局。在多带通用机上,一条纸带可以存放编码后的转移表,另一条存放被模拟的纸带,还有一条存放当前状态等临时信息。这些安排只是为了便于组织信息,并非实现通用性的必要条件。在单条纸带上,同样的信息可以放在由分隔符隔开的不同区域中。带标记的符号或相邻的标记用于指示被模拟机器的读写头位置,另外一些符号则用于区分程序文本和工作存储区。

一个模拟步骤可以分解为若干明确的操作。通用机先找到带标记的纸带符号,记录其编码值,再读取编码后的当前状态,并在转移表中查找与之匹配的指令。随后,它改写所表示的符号,更新状态的表示,并将读写头标记向左或向右移动。如果被模拟的读写头到达了显式表示的纸带区域边缘,模拟器就会扩展该区域,加入一个空白格的表示。在任何有限阶段,都只需表示有限多个格子。

设有一台机器,其规则是在状态 qq 下读到 11 时,写入 00,向右移动,并进入状态 rr。通用机不需要为这一特定组合配备专门的硬件规则。它只需读取指定 (q,1,0,R,r)(q,1,0,R,r) 的编码记录,并执行所需的记录和更新操作。提供不同的转移表,就能改变被模拟的行为,而模拟器本身保持不变。这正是解释执行指令与将每一种可能的指令都内置于有限控制器中的根本区别。

要证明这一构造的正确性,可以在被模拟机器的格局与模拟机器的格局之间建立一种关系。首先,通用机的编码格局必须表示以 xx 为输入的 MM。每完成一个模拟周期,都必须将 MM 的某个格局的表示转换为其后继格局的表示。最后,所表示的停机格局必须引出相应的输出或接受条件。随后,对模拟步数进行归纳,即可证明该构造对每一次有限计算都正确。

这种方法与编程语言的解释器十分相似,只是刻意采用了极为基础的形式。现代解释器使用更丰富的数据结构、内存管理机制和指令格式。通用机的证明表明,通用解释器的存在并不依赖这些便利条件。

不可判定性与模拟的局限

通用机能够执行指定的计算,但一般无法预先判定该计算将如何结束。最典型的例子是停机问题:给定 ⟨M,x⟩\langle M,x\rangle,判定 MM 在输入 xx 上是否最终停机。模拟提供了一种单向有效的方法。如果 M(x)M(x) 停机,通用模拟器最终就能观察到这一事件。如果它永远运行下去,那么无论等待多久,只要等待的时间有限,就无法凭借尚未停机这一事实断定它永远不会停机。

可以用对角线法证明,不存在通用的停机判定算法。假设有一个对所有输入都能终止的算法 H(p,x)H(p,x),当程序 pp 在输入 xx 上停机时,它正确地返回 11,否则返回 00。定义程序 DD:它以 pp 为输入,运行 H(p,p)H(p,p);如果结果是 11,就永远循环;如果结果是 00,就停机。若 dd 是 DD 的描述,那么它以自身描述为输入时的行为应满足

D(d) halts⟺H(d,d)=0.D(d)\text{ halts}\quad\Longleftrightarrow\quad H(d,d)=0.

然而,根据所假设的 HH 的正确性,又必须有:H(d,d)=1H(d,d)=1 当且仅当 D(d)D(d) 停机。这一矛盾表明,这样的 HH 不可能存在。

编码在这一论证中至关重要。程序必须能够表示为输入数据,其执行过程也必须能够通过有效过程重现。通用机恰好提供了这样的基础。自应用并不要求一台物理机器在内部实际容纳其整个运行机制的副本;它只要求程序的有限描述能够以字符串的形式传给某个程序。

图灵最初的不可判定性论证使用了“无循环”(circle-free)机器这一术语,讨论的是能否不断产生相关的输出符号序列。不应将这一论证与现代停机问题的证明逐字等同。不过,两种论证都利用有效描述和对角线推理,揭示机械程序的局限。随后,图灵将其机器模型与逻辑判定问题联系起来,证明一种通用的逻辑判定过程会使某个不可能解决的机器理论判定问题变得可解。

更一般的结果是赖斯定理:凡是仅取决于程序所计算的偏函数的非平凡性质,一般而言都是不可判定的。“非平凡”是指某些可计算偏函数具有该性质,但并非所有可计算偏函数都具有该性质。这排除了用一种通用算法判定任意程序的功能行为的可能性,但许多范围更窄的分析仍然可行。

这些结果并不意味着所有程序分析都是徒劳的。可以证明特定程序会停机,可以通过限制语言来保证终止,也可以利用形式验证,在明确的假设下证明某些性质。这里的局限针对的是这样一种单一过程:它总能终止,并能对每一个可能的程序及其输入,正确回答不加限制的一般性问题。

通用性、等价模型与有效转换

通用性是计算表达能力的一种性质,并不取决于某种特定的纸带布局。单带机与多带机、单向无限与双向无限的纸带,以及采用不同有限字母表的机器,都可以相互模拟。例如,可以将双向无限纸带上的非负位置与负位置交错排列,从而在单向无限纸带上表示它。多条被模拟的纸带可以用多条轨道或由分隔符划定的区域来表示,并用标记记录各个读写头的位置。这些变换会改变计算的开销,却不会改变哪些部分函数是可计算的。

同样的区分也适用于差异更大的计算模型。λ 演算、适当的寄存器机,以及存储空间无界的普通编程语言,都能表达同一类有效计算。要证明它们等价,需要给出有效的转换方法,而不能仅凭非形式化的相似之处。一个方向的转换可以把机器的转移表编译成程序;另一个方向则可以构造一个图灵机解释器,用来解释该程序的语法和操作规则。每种转换都必须保持相关的输出及不终止行为。

丘奇—图灵论题将这些数学上的等价关系与有效过程这一非形式化概念联系起来。它主张,任何能够通过有效机械方法算出的结果,都可以由图灵机计算出来。通用图灵机的存在,是形式模型内部的一条定理;而丘奇—图灵论题则是一项更广泛的主张,将该模型与一个形式化之前的概念视为等同。两者密切相关,但不应被当作同一个命题。

如果一个系统在适当的有效编码下能够表达任意图灵机计算,通常就称它具有图灵完备性。一种语言不必在形式上类似于机器的转移表,也能具有这一性质。条件控制和可操作的无界存储空间通常就已足够,即使其表面记法十分精简也是如此。反之,配置数固定且有限的有限状态机,本身无法支持不受限制的通用计算。它可以识别有用的模式,也可以控制物理过程,但不一定具有计算通用性。

必须仔细说明对资源的假设。所有实际计算机的内存都是有限的,因此,如果所有相关存储空间都有界,那么任何一台具体的物理设备都只有有限种数字配置。称其架构为通用架构,通常意味着考虑的是一个理想化的机器族,或者允许按需扩充内存。数学意义上的通用性,并不意味着一台有限设备能够完成所需存储空间超出其容量的计算。

对于其他模型,还需要作进一步限定。量子计算机使用量子态及其变换,但“通用量子计算”指的是以任意所需精度近似实现任意允许的量子计算的能力,而不只是经典通用机定义中的能力。对于以有限方式描述的标准量子计算,原则上可以进行经典模拟,只是代价可能极其高昂。因此,可计算能力相同,并不意味着实际效率也相同。

与存储程序和软件系统的关系

通用机表明,程序可以用与其输入相同的符号媒介来表示。这是将程序视为数据的概念基础。它的有限控制器执行固定的解释过程,而经过编码的机器描述则决定要进行何种计算。在表示层面上,程序与数据之间的区分并非绝对:指令和普通数据都是符号串。两者之所以发挥不同作用,取决于执行机制如何解释它们。

这一原理与电子计算机的存储程序组织方式有关,但两者并不相同。在冯·诺依曼结构中,指令和数据存放在同一个可寻址存储器中,由处理器取出并执行指令。图灵机的纸带本身不具备随机访问寻址能力,其基本操作也与中央处理器的基本操作有显著差异。此外,将代码与数据分开存储并不妨碍机器具备计算通用性。数学上的要求是能够以有效、可编程的方式进行模拟,而不是采用某种特定的物理存储布局。

因此,存储程序计算的发展史不能仅仅归结于通用机定理。1945年以约翰·冯·诺依曼名义传阅的《关于EDVAC的报告初稿》,成为一份对电子计算机组织方式具有重要影响的论述。图灵在1945年开展的自动计算引擎设计工作,同样着眼于实用的存储程序计算。这些进展不仅涉及解释编码指令在抽象意义上的可能性,还涉及存储技术、电子控制、算术运算以及工程经济性。

现代软件系统在多个层面体现了这些相关思想。解释器执行以另一种语言表示的程序。虚拟机提供抽象指令集或执行环境。仿真器则足够精确地复现另一硬件系统的行为,从而能够运行该系统的程序。操作系统负责管理资源并提供服务,但它并非通用机的另一种叫法:调度、保护、设备访问和文件管理,都是额外的组织管理职责。

编译器提供了从描述到执行的另一条途径。它不是在运行过程中反复对源程序指令进行解码,而是将程序翻译为另一种表示形式,通常是机器码。解释和编译都是对符号描述的有效变换。编译后的程序与解释执行的版本可能计算同一个函数,但在性能、内存使用和可观察到的交互方面存在很大差异。

仅凭通用性,无法保证这些工程属性。它不能说明一台机器速度快、可靠、安全、易于编程,或能够与某种特定设备通信。通用性也不要求代码能够自我修改。机器可以在整个执行过程中保持程序表示不变,同时仍然具备通用性。其关键能力在于,让任意有限描述支配一个可无限扩展的计算过程。

模拟开销与小型通用机

两台机器可以计算相同的函数,所需的资源却可能大不相同。计算复杂性研究的正是这类差异,包括运行时间和存储空间的差异。采用直接模拟方式的通用模拟器,可能每模拟一步都要扫描一张很长的编码转移表,还要反复遍历自身的纸带,以更新相距较远的信息。这些操作虽然不改变计算结果,却会使模拟过程比被模拟机器的运行更慢。

模拟开销取决于机器模型、表示方式,以及被模拟的机器是否固定。如果 MM 固定,且在输入 xx 上运行 tt 步,那么与其状态集和转移表有关的常数就可以并入一个依赖于 MM 的界中。如果 MM 的描述是可变输入的一部分,那么描述的长度也必须计入。混淆这两种情形,可能会使有关效率的结论显得比实际更强。初始解码的开销,以及表示原始输入所需的空间,也都是总成本的一部分。

经典的模拟结果说明了为何模型的选择至关重要。用单带机器直接模拟一台固定的多带机器,可能会产生平方量级的运行时间开销。如果模拟器有多条纸带,更精巧的构造就能取得更好的效果。1966 年的亨尼–斯特恩斯结果表明,在该定理的假设条件下,一台双带机器可以在 O(tlog⁡t)O(t\log t) 时间内,模拟一台运行时间为 tt 的固定多带机器。这类结果讨论的是机器模型之间的高效模拟;与仅仅断言通用机存在相比,它们给出了更具体的结论。

小型通用机提出了另一类优化问题:要实现通用性,有限控制部分究竟可以精简到什么程度?研究者统计状态数和纸带符号数,并在明确规定的约定下,寻找使这些数量尽可能少的构造。马文·明斯基在其 1967 年出版的《计算:有限机与无限机》一书中,提出了一台著名的七状态、四符号通用机。后续研究探索了状态数与符号数之间的其他权衡,以及对纸带初始环境的其他定义。

脱离这些约定,就不存在一个统一的“最小机器”问题。标准意义上的通用性通常要求:初始纸带上只有有限的输入,其余部分均为空白。而某些弱通用机的构造则假定纸带具有无限的周期性背景,另一些变体则以其他方式改变允许的初始条件。这种背景所提供的信息,可以减少必须编码到有限控制部分中的内容。因此,只有计算模型和输入假设一致时,状态数和符号数才可以直接比较。

结构紧凑也不一定意味着速度快。一台非常小的机器可能需要实现一长串层层嵌套的模拟,为了重现目标计算中的一次操作,就要执行许多基本步骤。实际处理器在许多方面采取了相反的做法:使用大量电路、存储层次结构和专用操作来降低执行成本。极小型通用机的主要意义,在于揭示通用计算如何能从极其有限的局部规则中产生。

自指、程序长度与数学应用

一旦机器描述可以作为数据来操作,程序就能推理其他程序的性质,也能以严格定义的方式推理自身描述的性质。这并不是普通计算之外的某种额外物理能力,而是有效编码、模拟以及通过算法构造新描述的能力所带来的结果。同一套机制既支持正面的构造,例如能自我复制的程序文本,也支持否定性结论,例如不存在通用的停机判定程序。

其中一个核心的形式化结果是克莱尼递归定理。它的一种标准表述是:在一个可接受的程序设计系统中,如果 ff 是程序索引上的全可计算变换,那么就存在一个索引 ee,使得

φe=φf(e).\varphi_e=\varphi_{f(e)}.

这里,φe\varphi_e 表示索引为 ee 的程序所计算的部分函数。这个等式说的是行为相同,并不要求程序文本完全一致。它表明,程序上的有效变换具有一个行为上的不动点。这为那些常被非正式地描述为“程序获取或使用自身描述”的构造提供了严格依据。

自我复制程序通常称为 quine,它们展示了程序文本与执行之间的一种相关区别。quine 能输出自身的程序文本,而不是简单地从外部来源读取这段文本。这类例子依赖于语言的引用和输出约定,而递归定理则是一般性的可计算性结论。两者都不意味着程序能够解决关于自身的任意问题。程序能够访问某种表示,并不能消除有关该表示所描述行为的不可判定性障碍。

通用机也是柯尔莫哥洛夫复杂度的基础;后者衡量有限对象的最短有效描述的长度。对于选定的通用描述系统 UU,一个基本定义是

KU(x)=min⁡{ ∣p∣:U(p)=x }.K_U(x)=\min\{\,|p|:U(p)=x\,\}.

在无前缀版本中,有效的停机程序构成一个无前缀集合,而 KK 通常表示相应的复杂度。在适当的通用性假设下,更换参照机器所引起的复杂度变化,至多是一个与 xx 无关的加法常数。一个固定的解释器可以把某个系统中的描述转化为另一个系统中的计算,这就解释了这项常数开销。

不过,对于短字符串,参照机器的选择仍可能产生显著影响,而且精确的柯尔莫哥洛夫复杂度一般不可计算。仅仅运行所有短程序,无法确定那些尚未结束的程序中,没有任何一个会在之后输出目标字符串。这使描述长度与通用模拟的局限直接联系起来。实际的数据压缩方法利用的是特定的规律和可计算的编码过程,并不是在计算任意字符串所能对应的最短程序。

通用模拟也是数学归约中的标准工具。新构造的机器可以先模拟给定的程序,然后在该模拟停机时执行某个指定动作。这样,它的行为就把关于一个计算问题的疑问转化为关于另一个计算问题的疑问。明确构造这类模拟器,能够使不可判定性的论证变得严谨:归约必须有效地变换每个输入,而得到的机器必须恰好具有证明所要求的行为。