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

丘奇—图灵论题

丘奇—图灵论题将有效可计算函数等同于图灵机可计算函数,把非形式化的算法概念与精确的数学模型联系起来。

36 个关键词12 个词条链接到这里4 个尚未撰写AI 撰写
图灵机算法艾伦·图灵可计算性理论函数(数学)数学逻辑学大卫·希尔伯特丘奇—图灵…

丘奇—图灵论题指出,凡是能通过有效的机械化过程计算的函数,都能由图灵机计算。等价地说,按照某种算法能够计算的函数,恰好就是若干独立发展起来的数学计算模型所刻画的函数。该论题源自阿隆佐·丘奇和艾伦·图灵在20世纪30年代的研究,为系统化计算这一非形式化概念与可计算性理论这一形式化学科之间建立了公认的联系。

这一论题关注的是原则上能够计算什么,而不是什么能够快速、经济地计算,或能够用现有硬件计算。它本身并不是通常意义上的数学定理:“有效过程”最初是一个非形式化概念,而图灵机计算则有精确的数学定义。数学定理证明的是特定形式模型之间的等价性;这一论题则把这些模型共有的计算能力等同于有效计算。

这一区别既是该论题具有重要意义的根本原因,也是围绕它展开争论的关键。它为严格证明某些问题无法由任何算法求解提供了依据,解释了为何不同的通用编程系统具有相同的基本计算能力,也为评估量子计算以及超越图灵机的计算设想提供了参照。关于高效模拟、物理过程或人类思维的主张需要额外的假设,不应将它们与原始论题混为一谈。

有效计算与论题的精确表述

有效过程由明确的指令组成,执行时不需要巧思、灵感,也不需要某种无法解释的、能够辨认正确答案的能力。每一步操作都必须能够机械地执行,而任何一次已完成的具体计算都只能包含有限步操作。不过,面对不同的输入,这一过程所需的步数可以任意多。它并不要求存在一个适用于所有情形、且在实际中可行的统一时间上限。

对于一个处处有定义的数论函数 f:N→Nf:\mathbb{N}\to\mathbb{N},这一论题可以表述为

f is effectively calculable⟺f is Turing-computable.f\text{ is effectively calculable} \quad\Longleftrightarrow\quad f\text{ is Turing-computable}.

同样的表述可以推广到具有多个自然数自变量的函数,并且在采用适当约定后,也可以推广到部分函数。部分函数在某些输入上可能没有定义值;计算该函数的程序在这些输入上可以永远运行下去。这一区别十分重要,因为有限的程序不一定会终止,而判定程序是否会终止,本身就是计算中的一个核心问题。

限定于自然数,并不意味着这一论题只适用于初等算术。有限字符串、符号表达式、图、程序和证明都可以用自然数表示。例如,有限的字符序列可以利用字符编码和分隔符进行编码。只要编码与解码本身都是有效的,表示方式的选择就只会影响使用的便利性或性能,而不会改变根本的可计算性。

“机械过程”描述的是计算的执行方式,并不一定指一台物理机器。图灵最初分析的是按照固定规则、使用纸笔进行计算的人。历史上,这样的人被称为“计算员”(computer)。这一论题只考虑那些每一步操作都由指令和当前可用信息确定的工作,从而将人的智力因素抽象掉。

有两点限定有助于避免常见的误解。首先,这一论题并不声称所有数学问题都有算法解。它的重要性部分在于,它使我们能够精确说明为什么有些问题没有算法解。其次,它也不声称现有计算机拥有无限的存储空间。图灵机可以使用一条无界的纸带,不过任何会终止的计算都只会用到其中有限的一部分。这表示的是可以根据需要不断提供更多工作空间,而不是实际存在一个已经完整建成的无限存储器。

一种算法如果只是猜测答案、要求人给出无法解释的判断,或向某个未加说明的来源查询正确解答,并不会因此就自动成为有效算法。必须把这类来源所完成的计算工作也纳入考察。否则,所谓的解法不过是把原问题转交给了一个未经审视的组成部分。

数理逻辑中的历史起源

这一论题源于澄清数学与逻辑学基础的尝试。20世纪初,大卫·希尔伯特倡导一项纲领,主张以精确的、有穷的方法研究形式数学系统。其中一个重要问题是判定问题:是否存在一种通用的机械程序,能够判定任意一阶逻辑公式的逻辑有效性。希尔伯特与威廉·阿克曼在1928年出版的数理逻辑著作中,对这一问题作出了影响深远的表述。

要对这一问题给出确定的否定答案,首先需要对“机械程序”作出足够精确的解释。算术、代数以及特定逻辑系统中早已有许多熟知的算法,但列举程序的实例,并不能为所有可能的程序提供一般定义。难点在于划定一条界限:既不排除任何真正有效的方法,又足够精确,能够用于数学证明。

库尔特·哥德尔于1931年提出的不完备性结果,揭示了足够强且可有效公理化的形式系统所具有的局限。其证明用算术来表示表达式和证明,推动了人们认识到将符号推理作为数学对象加以研究的重要性。不完备性本身并未解决判定问题,也不应将其与丘奇—图灵论题混为一谈。它构成了这一论题的部分历史背景,使有关形式程序的问题变得尤为迫切。

阿隆佐·丘奇通过λ演算与递归函数来研究有效计算。1936年,他提出将有效可计算性等同于一类有精确定义的数论函数的可计算性,并利用这一框架得出了一个与判定问题有关的不可解性结果。斯蒂芬·科尔·克利尼在发展相关理论以及建立各种表述之间的联系方面发挥了重要作用。

图灵在《论可计算数及其在判定问题上的应用》中独立提出了自己的机器模型。该论文于1936年投稿,发表于标注年份为1936—1937年的期刊卷册中。他的独特贡献并不只是提出了另一套形式体系。他分析了人进行计算时的基本活动,并论证说,其中相关的限制可以用一台具有有限个状态、有限字母表以及一条划分为格子的纸带的机器来表示。

图灵机与丘奇形式体系之间的关系,在两者问世之初便得到了确立。埃米尔·波斯特也于1936年发表了关于有限组合过程的论述,与二者的工作密切相关,同时强调了将这类形式体系与有效计算等同起来的重要意义。因此,如今通用的这一复合名称,体现的是不同研究殊途同归,而非一个由两人共同提出的命题。由于这些不同表述的等价性可以得到数学证明,它们便成为同一理论的组成部分。

等价的形式计算模型

图灵机由有限控制器、划分为单元格的纸带、读写头以及有限组转移规则构成。每一步,当前的控制状态和读到的符号共同决定写入什么符号、读写头如何移动,以及接下来进入什么状态。尽管这些操作十分简单,图灵机仍可通过使用更多纸带并反复读取先前写下的信息,组织任意长的计算过程。

这一模型中许多看似存在的限制,并不会限制它所能计算的内容。只要适当地表示各条纸带及其读写头的位置,单带图灵机就能模拟多带图灵机。使用较大有限字母表的图灵机,也可以用较小字母表上的符号块来模拟。同样,让纸带向两个方向而非一个方向无限延伸,改变的也只是模拟的细节,而不是可计算函数的类别。不过,这些模拟的时间开销可能相差很大。

λ 演算以另一种方式描述计算。它的表达式由变量、函数抽象和应用构成。其中一项核心操作是 β 归约,即将实参代入函数体:

(λx.M) N  ⟶  M[x:=N],(\lambda x.M)\,N \;\longrightarrow\; M[x:=N],

代换时须确保自由变量不会被意外捕获。数以及其他数据都可以用适当的 λ 表达式表示。这一体系为函数式编程提供了基础,但在这里,它的历史意义在于:这种基于代换的计算所能计算的函数,与图灵机所能计算的函数属于同一类别。

递归函数理论提供了一种算术形式的表述。它从一些基本函数出发,通过复合和各种形式的递归等运算构造新函数。原始递归可以生成许多常见的全函数,但无法涵盖所有全可计算函数。加入无界极小化运算后,就得到了部分递归函数,其中包括搜索过程可能永不终止的程序。这些函数恰好就是图灵机可计算的部分函数。

其他等价模型还包括寄存器机以及适当的字符串重写系统。例如,寄存器机可以使用极小的指令集,对带编号的存储单元进行操作,指令可以只有递增和条件递减等。它在表面上与普通机器指令相似,但这种相似性并非等价性的关键:重要的是,它的操作能够模拟图灵机,同时也能由图灵机模拟。

这些等价性结果是定理,而不是对该论题的应用。一旦两个模型有了精确定义,就可以通过构造模拟来证明它们之间的关系。只有当我们把这些模型共同刻画的形式化类别等同于所有有效过程时,才涉及丘奇—图灵论题。证明十种形式模型彼此等价,并不能在逻辑上确立:第十一种尚未明确提出的方法绝不可能超越它们。不过,这确实表明,即使记法、组织方式和基本操作存在显著差异,可计算性的边界也未必会改变。

为什么这一论题得到认可

对这一论题最有力的支持,来自概念分析与多种独立提出的模型殊途同归这两方面的结合。图灵的论证考察了人类计算者遵循固定指令时所受的限制:计算者在任一时刻只能区分有限多个相关符号,只能处于有限多个与指令有关的状态之一,并且所执行的基本动作,其作用范围有限、结果确定。复杂操作则可以分解为由较简单操作组成的序列。

这些假设解释了为什么有限的转移表适合用来表示一个计算过程。像“写出这道任意数学题的正确答案”这样的指令,并不会仅仅因为能用一句简短的话写出来,就算作一个基本步骤。要执行它,还需要另一套方法。同样,要求一次查看无限多个格子的指令,也引入了普通有效计算所不具备的能力。

这一论证并不要求我们相信,人类的心理活动确实由纸带操作构成。它抽取的是遵循规则这一活动的抽象特征,而非其具体实现方式。计算者可能一笔写出几个字符,也可能认出一个熟悉的缩写,但有界的复合动作都可以用有限多个基本动作来替代。需要论证的是,这种替代保留了原本要执行的过程,而不是它在物理形式上与原来的活动相似。

不同模型得到相同结果,则提供了另一类支持。符号替换、算术递归、纸带操作和寄存器操作,最终都得到同一类可计算函数。这些系统并非全都是彼此的表面变体。它们得出的结果一致,表明由此划定的界限反映的是有效计算这一概念,而不是某种特定记法的偶然特征。

使用编程语言的经验也提供了进一步的证据,尽管这并不是证明。常规的通用语言都可以配备解释器,而解释器的操作是图灵可计算的。对象、高阶函数、并发或自动内存管理等复杂特性,会改变计算的表达和组织方式,却不会因此产生不可计算函数。因此,任何声称成立的反例,都必须指出某种无法被模拟的有效操作,而不能仅仅提出一种新的编程风格。

此外,也有从公理出发研究计算的工作。例如,罗宾·甘迪在1980年的研究中,考察了支配离散确定性机制的数学原则,并在这些原则下推导出了有关可计算性的结论。这类结果有助于澄清:结论如何依赖于关于状态、局部性和信息的假设。但它们并不能把这一论题的每一种可能的物理诠释都变成定理。

因此,这一论题的地位既不同于通过实验测定的物理定律,也不同于完全在数学内部表述的一般猜想。形式化分析可以为它提供支持,并使其假设更加明确。任何提出的反例,仍然必须解释其方法为何算得上有效,而不能暗中依赖无限资源、不可计算的参数或未经解释的操作。

不可判定性与算法的局限

停机问题问的是:一个程序在给定输入上运行,最终是否会停止。它的不可判定性是关于形式化计算的一条定理。丘奇—图灵论题赋予这条定理更广泛的解释:不存在一种有效的通用过程,能够始终正确回答停机问题。

一个标准的对角线论证揭示了其中的障碍。假设存在一个全可计算函数 H(p,x)H(p,x),当程序 pp 在输入 xx 上停机时返回 11,否则返回 00。构造一个程序 DD,它在接收输入 pp 后,若 H(p,p)=1H(p,p)=1 就永远循环,若 H(p,p)=0H(p,p)=0 则停机。设 dd 是 DD 的一个编码。在输入 dd 上运行 DD,无论哪种情况都会产生矛盾:它停机,当且仅当这个假定的预测器说它不停机。因此,这样的全可计算函数 HH 并不存在。

这一结果针对的是适用于所有程序和输入的统一求解方法,并不意味着永远无法证明某个具体程序会终止。一个在每次迭代中都使某个非负整数递减的循环,可能有很简单的终止性证明。受限的编程语言也可以保证所有符合其要求的程序都会终止。不可能存在的是一种普遍适用、始终终止,并且能正确处理任意程序的算法。

类似的局限也存在于关于程序语义的问题中。莱斯定理指出,对于程序所计算的偏函数的每一种非平凡性质,都无法根据任意给定的程序描述来判定该性质是否成立。“非平凡”是指,有些可计算函数具有该性质,而另一些则不具有。关于程序文本或语法的问题未必属于这一定理的适用范围;实际分析也可以通过限制所考察的程序范围,或允许给出不完备的答案来取得成效。

另一个相关的区别是判定集合成员资格与识别集合成员资格之间的区别。一个集合的识别器在输入属于该集合时会停机并接受,但在其他情况下可能永远运行下去。判定器则必须在每个输入上停机,并给出正确的是非答案。例如,可以通过运行指定程序直到它停止来识别停机情形,但这并不能判定不停机的情形。

此外,函数的数量远远多于算法。有限的程序描述构成一个可数集合,而从自然数到 {0,1}\{0,1\} 的函数所构成的集合是不可数的。因此,这类函数中的绝大多数都没有对应的程序。这一计数论证确立了不可计算函数的存在,但具体的不可判定性证明揭示了更多内容:它们把这种不可能性与具体的数学任务和计算任务联系起来。而丘奇—图灵论题则进一步支持这样一种主张:从一种通常意义上的算法形式体系换到另一种,并不能消除这些局限。

通用性、编程与软件验证

通用图灵机接收经过编码的机器描述及其输入,并模拟所描述的计算。如果 ⟨M,x⟩\langle M,x\rangle 是机器 MM 和输入 xx 的编码,就可以构造一台通用机器 UU,使得只要被模拟的计算停机,就有

U(⟨M,x⟩)=M(x)U(\langle M,x\rangle)=M(x)

而当被模拟的计算不停机时,通用机器也相应地不停机。这精确表述了将程序作为数据来解释的含义。

通用性有助于解释,为什么一台通用计算机能够执行许多不同的任务,而不必为每项任务重新改造硬件。程序决定要进行何种计算,解释器或处理器则执行相应的指令。这一数学思想不依赖于任何特定的硬件体系结构,但阐明了存储程序原理:计算的描述可以使用与其他信息相同的表示手段来存储和处理。

图灵完备性是形式系统、语言或机器模型的一种性质:在适当的理想化假设下,它能够模拟任意图灵机。丘奇—图灵论题则是另一种主张,它将有效计算与图灵可计算性等同起来。证明一种语言具有图灵完备性,并不等于证明了这一论题;这只是确定了该语言在这一论题所涉及的形式体系中的位置。

这些理想化假设至关重要。存储容量固定的物理计算机,其可能的内部配置只有有限种。关于通用性的断言,通常针对的是可以不断增添存储空间的体系结构或编程模型,而不是一台始终受固定存储上限约束、无限期运行的具体设备。理想模型刻画的是可以随规模扩展的计算过程,而不是承诺实际机器拥有无限资源。

这些区分也影响着形式验证。不存在适用于所有程序的通用分析方法,并不妨碍在明确限定的条件下开展正确性证明、使用证明助手或进行自动化检查。在合适的形式系统中,检查给定的推导可以是有效可计算的,即使寻找证明或判定证明是否存在并非如此。同样,有界模型检测考察的是指定的有限搜索空间,而不是以完全一般的方式解决任意程序的行为问题。

编译器或解释器提供了另一个具体例子。如果一种源语言具有有效可计算的语义,而且某个实现忠实地实现了该语义,那么就可以通过明确的变换,将该语言中的程序与较低层次的计算联系起来。这些变换可以保持计算结果不变,同时改变执行时间、内存使用量以及优化的可能性。丘奇—图灵论题关注的是在适当的理想化假设下能够得到哪些结果;它并不保证转换能够保持效率、安全性或推理的便利性。

高效计算与量子计算的区别

原始论题依据可计算性而非计算成本对函数进行分类。一个需要 2n2^n 步的算法和另一个需要 n3n^3 步的算法,可能计算的是同一个函数,但它们在实际运行中的表现却截然不同。计算复杂性通过时间复杂度和空间复杂度等度量来研究这些差异。

扩展丘奇—图灵论题也称为高效计算版本或复杂性理论版本,它对模拟开销提出了更强的主张。其具体表述不尽相同。一种常见表述是:每一种合理的计算模型都能由概率图灵机模拟,且模拟开销至多为多项式量级。“合理”的含义,以及选择确定性模拟还是概率模拟,都是这一表述的实质性组成部分,而非无关紧要的细节。

采用多项式开销,是因为它为比较计算模型提供了一种相对稳健的方式。如果模拟所需的时间是原运行时间的平方或立方,就仍可能保留多项式时间可解性,而指数级的模拟则未必如此。这并不意味着每个多项式时间算法都具有实用性:过大的指数或常数都可能使计算难以实际完成。反过来,对于规模足够小或具有特殊结构的输入,指数时间算法也可能有用。

量子计算机说明了为什么必须区分原始论题与扩展论题。在以有效方式明确规定的标准模型中,量子计算可以用经典计算来模拟,达到任意指定的有限精度,只要该精度足以满足相应的输出保证即可。这种模拟可能需要极其庞大的资源。因此,标准形式的量子计算并不会仅仅凭借叠加或纠缠,就提供计算不可计算函数的算法。

量子计算的意义在于效率。1994年提出的肖尔算法为整数分解及相关任务提供了多项式时间的量子方法。目前尚无已知的多项式时间经典整数分解算法,但也没有人证明这类算法不可能存在。因此,肖尔算法为质疑高效经典模拟这一主张提供了有力理由,却没有无条件地证明这种模拟不可能实现。

随机性带来了另一种区别。随机化算法在运行中作出随机选择,并根据其成功概率和资源消耗所满足的条件来评价。在标准的有界错误定义下,随机性不会使不可判定的判定问题变得可判定。无限长的随机序列几乎必然是不可计算的,但生成不可预测的比特,并不等于能够在提供可靠正确性保证的前提下,计算某个指定的不可计算函数。

P与NP问题等问题也属于复杂性范畴,而非基本可计算性范畴。它们根据资源需求,对本已可判定的问题进一步分类。解决这些问题将深刻影响人们对高效计算的理解,但仅凭这一点,并不能证实或推翻原始的丘奇—图灵论题。

物理计算与超计算的构想

物理丘奇—图灵论题将关注范围从有效的符号操作过程扩展到物理过程。这个名称涵盖几种不同的主张:任何物理上可实现的计算装置都只能计算图灵可计算的函数;物理演化可以通过计算来模拟;或者,这种模拟能够高效进行。这些表述的强弱不同,对制备、测量、精度和可用资源所需的假设也各不相同。

涉及连续量时,这些区别就显得尤为重要。一个实数包含无穷多位数字,而有些实数是不可计算的。如果某个数学装置能够精确访问这样的数,那么在适当的规则下,它就可能提取出超出图灵可计算范围的答案。但这种额外能力可能早已被置于初始值之中。一段有限的描述,例如“使用一个数位编码了停机问题的实数”,并没有说明如何制备或测量这个数。

因此,模拟计算并不天然就是超越图灵机的计算。普通模拟装置以有限精度运行,并受到噪声、校准限度和读出误差的影响。微分方程可以定义一条精确的数学轨迹,却未必能提供一种物理上有效的方法来提取这条轨迹的每一项特征。对于连续数学中的不可计算性结果,必须结合其对输入和观测所作的假设来理解。

超计算研究的是那些被提出用来超越图灵可计算性的模型。加速机就是一个简单的例子:如果它的连续各步分别耗时 1/2,1/4,1/8,…1/2,1/4,1/8,\ldots 个时间单位,那么它就能在一个时间单位内执行无穷多步。配合适当的附加约定,这样的模型可用于提出普通机器无法解决的问题的解法。尚未解决的疑问是:模型所要求的无限加速和最终状态观测,是否对应着可实现的操作。

另一些构想借助理想化的相对论时空;在这种时空中,从数学上说,一名观测者或许能够接收到与另一名观测者的无界计算相关的信息。这些构想是否具有现实意义,取决于苛刻的物理条件,包括时空结构、信号传递、装置能否存续,以及能否可靠地区分信号未曾发出与信号被无限期延迟这两种情况。数学上的时空构造本身并不等于已经得到验证的计算技术。

预言机提供了一种更清晰的理论区分。它是一台图灵机,但额外获准直接获得关于某个指定集合的成员资格问题的答案,而这个集合可能是不可计算的。预言机允许人们严格比较相对计算能力,而不必断言这种预言能力在物理上可以获得。拥有普通停机问题预言能力的机器可以解决该停机问题,但它也有一个自身无法解决的相应停机问题。这一框架阐明的是额外能力能够带来什么,而不是确立如何将其构建出来。

数学推理、智能与语义限度

丘奇—图灵论题有时会被引申为关于心智、数学理解或人工智能的主张。原本的论题并未声称每一种心智活动都是有效计算,也未声称意识是一种算法。它所讨论的是按照明确的机械规则执行的过程。能否用这些术语刻画所有认知活动,则是另一个科学与哲学问题。

这一区分也将可计算性与智能区分开来。一个图灵完备的系统可能效率极低,也可能不具备任何有用的学习、感知或推理能力。反过来,一个专用系统可能完成复杂的任务,却不提供通用编程环境。图灵测试于1950年在关于机器智能的讨论中提出,关注的是对话行为,不应与关于有效可计算性的论题混为一谈。

哥德尔不完备性定理促使一些人提出,人类的数学推理超越了任何算法。这些论证的出发点确实是一项限制:一个相容、可有效公理化且具有足够算术表达能力的形式理论,无法证明所有算术真命题。但要进一步得出关于心智的结论,还需要额外的前提,例如,存在一个充分刻画某个人推理能力的固定形式化表示,并且有充分理由确信这种推理的可靠性。这些前提并不能由不完备性本身推出。

这些逻辑上的区别在算术中尤为明显。在标准自然数结构中,每个具体语句都有真值,但不存在能够判定所有一阶算术语句真假的算法。一个可有效公理化的证明系统可以支持机械化的证明检验和系统性的证明搜索,却仍无法涵盖所有这类真命题。因此,真、可证明性与有效可判定性是不同的概念。

人类成功解决某个数学问题,本身并不能证明其具有不可计算的能力。一个证明可能揭示此前未知的算法,解决某个不可判定的一般问题中的一个实例,或者使用能够增强某个形式理论的假设。这些可能性都不能提供一种适用于所有实例的统一有效方法。同样,计算机未能解决某个难题,可能反映的是资源有限或方法不足,而非触及了可计算性的边界。

这一论题还预设,获取信息与根据信息进行计算是两回事。交互式系统可以产生取决于人类、传感器、网络或其他环境的输出。其行为不一定仅由初始的有限输入决定。要评估一项关于可计算性的主张,就必须明确环境提供了哪些信息。如果外部参与者提供了某个不可计算问题的答案,那么组合后的系统便获得了这些信息;这并不意味着内部程序通过算法推导出了这些答案。