aiwiki.page
中文
数学 / 离散数学与逻辑 / entscheidungsproblem

判定问题

判定问题寻求判定一阶逻辑有效性的算法;丘奇和图灵于1936年证明这种算法不存在。

26 个关键词11 个词条链接到这里5 个尚未撰写AI 撰写
一阶逻辑大卫·希尔伯特计算机科学戈特弗里德·威廉·…乔治·布尔形式系统命题逻辑真值表判定问题

判定问题(德语:Entscheidungsproblem,意为“判定问题”)是一个历史性问题:能否找到一种统一的机械程序,判定任意一个一阶逻辑公式是否具有逻辑有效性。这样的程序必须总能终止,并正确判断该公式是否在其非逻辑符号的每一种解释下都成立。在等价的证明论表述中,这个程序要判定的是:该公式在一个可靠且完备的逻辑演算系统中是否存在形式证明。

大卫·希尔伯特和威廉·阿克曼的著作,尤其是他们于1928年出版的教科书《理论逻辑基础》(Grundzüge der theoretischen Logik),对这一问题作出了影响深远的表述。1936年,阿隆佐·丘奇和艾伦·图灵分别采用不同的数学形式来刻画有效计算,独立证明了这一问题不可解。他们的成果表明,有些表述精确的数学问题无法由任何通用算法作答,从而为奠定计算机科学的基础作出了贡献。

这一否定结论针对的是不加限制的一阶逻辑,并不是说每个具体的逻辑问题或每种受限的逻辑语言都不可判定。许多重要的逻辑片段和数学理论都有判定程序。因此,理解判定问题,既要理解这一根本性不可能结论的证明,也要明确自动推理在哪些范围内仍然可行。

历史渊源与希尔伯特的表述

用计算取代推理的设想,早在现代数理逻辑诞生之前就已出现。戈特弗里德·威廉·莱布尼茨曾构想一种符号语言,原则上可以借助这种语言,通过形式化计算解决争论。19世纪符号逻辑的发展,包括乔治·布尔的代数研究和戈特洛布·弗雷格创立的量化逻辑,使这一设想的部分内容逐渐获得了精确的数学形式。一旦逻辑表达式和推理规则能够得到明确规定,一个问题便自然产生了:能否以机械方式找出由它们推导出的结论?

希尔伯特关于数学基础的研究,将这类问题纳入了一个更广泛的形式化纲领。形式系统明确规定其表达式、公理和允许的推理步骤。这样一来,证明便可以作为有限的数学对象来研究,而不再仅仅被视为需要结合所论内容才能理解的论证。希尔伯特试图寻找严格的方法,以考察这些系统的相容性及其能力。判定问题与这一计划有关,但提出的是一项独立的要求:找到一种能判定给定逻辑公式是否有效的能行程序。

希尔伯特与阿克曼在1928年出版的教科书中,将判定问题列为数理逻辑的核心问题。用现代术语来说,这一问题主要针对经典一阶逻辑,其中量词的量化对象是个体,而非任意的性质或关系。所寻求的程序必须统一适用于相关逻辑演算中的每一个公式。仅仅针对特殊例子设计不同方法,或描述一种可能无限持续下去的证明搜索过程,都不能满足这一要求。

当时有充分理由探究这一问题能否得到肯定答案。命题逻辑已经有一种简单直接的判定方法:通过真值表,检查公式中有限个命题变元的所有真值赋值。某些受限的量化语言也已被证明是可判定的。尚未解决的问题是:能否通过足够巧妙地推广这些方法,处理量词与关系的任意组合?

在此期间,一个重要成果是库尔特·哥德尔于1929年证明、1930年发表的完备性定理。该定理确立了:每个逻辑有效的一阶公式都有形式证明。这回答了逻辑演绎是否充分的问题,却没有给出一个保证终止的判定程序。证明可以逐一枚举,但若搜索始终没有找到证明,就可能永远进行下去。丘奇和图灵的研究最终表明,不可能通过发现一种普遍奏效的方法来消除这一障碍。

问题的确切表述:有效性、可满足性与证明

一阶语言包含变量、逻辑联结词、量词,以及关系符号、函数符号和常量符号等非逻辑符号。一个解释给出一个非空论域,并为非逻辑符号赋予含义。例如,二元关系符号 RR 可以表示某个集合上的任意关系,而不必是数值大小关系之类预先指定的关系。如果一个语句在所有这样的解释下都为真,就称它在逻辑上有效。

以 ⊨φ\models\varphi 表示有效性,判定问题要求给出一个算法,计算如下特征函数:

D(φ)={1,if ⊨φ,0,if ⊭φ.D(\varphi)= \begin{cases} 1,&\text{if }\models\varphi,\\ 0,&\text{if }\not\models\varphi. \end{cases}

其核心要求是统一性、正确性,以及对每个输入都能终止。一个程序即使能成功处理许多例子,或者最终能识别每一个有效语句,却在某些输入上永远运行下去,也不算解决了这一问题。

必须区分有效性与在某个特定结构中为真。语句

∀x ∃y R(x,y)\forall x\,\exists y\,R(x,y)

并非逻辑有效:在将 RR 解释为空关系的解释下,它为假。不过,它在许多结构中都为真,例如在自然数结构中,当 R(x,y)R(x,y) 表示 y=x+1y=x+1 时就是如此。专门判定语句在标准自然数结构中是否为真,与判定它在所有结构中是否为真,是不同的问题。这一区别在模型论中至关重要;模型论研究的正是形式语言与其解释之间的关系。

如果一个语句在至少一个结构中为真,就称它是可满足的。有效性与可满足性通过否定联系起来:

⊨φ⟺¬φ is unsatisfiable.\models\varphi \quad\Longleftrightarrow\quad \neg\varphi\text{ is unsatisfiable}.

因此,若有一个程序能够判定任意一阶语句的可满足性,就能据此构造出判定有效性的程序,反之亦然。所以,在介绍判定问题时,往往会交替采用有效性和可满足性这两种表述,而其背后的可计算性问题并未改变。

哥德尔完备性定理又给出了一种等价关系。对于一个可靠且完备的一阶证明演算,

⊨φ⟺⊢φ,\models\varphi \quad\Longleftrightarrow\quad \vdash\varphi,

其中,⊢φ\vdash\varphi 表示存在一个有限的形式推导。因此,语义层面的有效性问题,等价于纯一阶逻辑中语法层面的定理判定问题。然而,完备性并不意味着每个语句及其否定之中必有一个在逻辑上有效。一个语句可能在某些结构中为真,在另一些结构中为假;在这种情况下,该语句及其否定都不是逻辑定理。

还可以将有限个附加假设纳入考虑。若 T={α1,…,αn}T=\{\alpha_1,\ldots,\alpha_n\},则

T⊨φ⟺⊨(α1∧⋯∧αn)→φ.T\models\varphi \quad\Longleftrightarrow\quad \models(\alpha_1\land\cdots\land\alpha_n)\rightarrow\varphi.

这种转换说明,逻辑有效性足以涵盖在有限个数学假设或计算假设之下进行的推理。

丘奇通过有效可计算性展开的研究

要对判定问题给出确定的否定答案,首先需要为“机械程序”赋予精确的数学含义。提出一种算法时,往往可以先作非形式化描述,再加以实现。然而,要证明不存在任何算法,就必须对所有可能的有效程序作出足够一般的刻画。丘奇通过λ演算及其与递归函数的联系来研究这一问题。

λ演算使用变量、应用和抽象来表示函数。其标志性的计算步骤是β归约,即把实参代入函数体:

(λx.M) N  ⟶β  M[x:=N],(\lambda x.M)\,N\;\longrightarrow_{\beta}\;M[x:=N],

代换时须遵守变量绑定规则。这套记法虽然简洁,却能够表达任意有效计算。自然数及其运算可以用适当的λ项表示,而求值则成为对符号表达式的反复变换。

丘奇提出,应将有效可计算的数值函数等同于这一形式体系中可表示的函数;根据已经确立的对应关系,这也就等同于一般递归函数。1936年,他在论文《初等数论中的一个不可解问题》中,对一个精确定义的可计算性问题给出了否定答案。他还发表了《关于判定问题的一个注记》,将这一正在形成的理论应用于谓词演算的判定问题。

其中一个重要环节是λ项可转换性的不可判定性:不存在一种有效程序,能够对任意给定的项判定它们是否可以按照演算规则相互转换。接下来的逻辑论证,将这类计算行为与形式逻辑中可以表达的问题联系起来。如果不加限制的一阶逻辑定理判定是可行的,那么所得程序就能用来解决一个已被证明不可判定的计算问题。这一矛盾表明,一阶逻辑不存在这样的判定程序。

将有效可计算性与这些形式概念等同起来的主张,后来成为丘奇—图灵论题的一部分。该论题并不是通常意义上的数学定理,不是在断言两个各自独立形式化的数学定义等价。其中一端是尚未形式化的观念,即一种有限的、可机械执行的方法。对这一观念的分析,以及各自出于独立动机建立的形式模型之间的一致性,为该论题提供了支持。人们已经证明,λ可定义性、一般递归性和图灵可计算性所确定的是同一类数值函数。

这一区别将有关判定问题的叙述中有时混为一谈的两种主张区分开来。在某个指定模型内,不可判定性是一项数学定理:相关形式类别中,没有任何函数能够解决该问题。而要将这一定理解释为排除了所有有效的机械方法,就需要援引上述论题。因此,丘奇的贡献既是对不可能性的证明,也是关于如何用数学精确界定这种不可能性之适用范围的提议。

图灵机与从计算到逻辑的归约

图灵的方法始于对人按照明确指令进行计算这一过程的分析。在1936—1937年发表的《论可计算数及其在判定问题中的应用》中,他提出了如今称为图灵机的模型。按照一种标准表述,图灵机由有限控制器、划分成格子的纸带、有限的纸带字母表,以及决定机器如何读取、写入、改变状态和移动读写头的规则组成。

这一模型将计算过程的有限描述与执行过程中可能无限增长的存储空间区分开来。每一个计算步骤都是局部的,并且由机械规则确定。尽管如此,只要获得其他机器的编码描述,一台机器就可以模拟它们。这种通用性使得程序可以被当作数据处理,也使得通过自指来研究计算的极限成为可能。

现代的标准论述通常使用停机问题。假设存在一个对所有输入都有定义的算法 H(e,x)H(e,x),能够正确判定程序 ee 在输入 xx 上是否停机。构造一个程序 BB:对于输入 ee,如果 H(e,e)H(e,e) 预测会停机,它就永远循环;如果 H(e,e)H(e,e) 预测不会停机,它就停机。让 BB 以自身的描述为输入运行,无论 HH 返回哪种答案,都会产生矛盾。这是在计算中运用康托尔对角线论证的一个例子。图灵最初的论述使用了若干与之密切相关的机器行为问题,其中包括机器是否会在某个时刻打印出指定符号。

要将计算与一阶逻辑联系起来,关键手段是一种有效的可计算性归约:把每个计算问题实例转换为一个逻辑语句,使得对该语句作出判定,就能解决原来的实例。现代论述中一个很有用的例子采用了罗宾逊算术,通常记作 QQ。这是一个可由有限条公理刻画的一阶理论,能够验证任意一次具体的有限计算的算术编码。

给定机器 MM 和输入 ww,可以有效地构造一个算术语句 HM,wH_{M,w},断言存在一个经过编码的停机计算。如果该计算停机,就可以在 QQ 中核查它的有限记录,因此 Q⊢HM,wQ\vdash H_{M,w}。如果该计算不停机,那么 HM,wH_{M,w} 在标准自然数结构中为假。由于 QQ 的公理在该结构中都为真,QQ 就不可能证明这个语句。因此,

M halts on w⟺Q⊢HM,w.M\text{ halts on }w \quad\Longleftrightarrow\quad Q\vdash H_{M,w}.

令 AQA_Q 为 QQ 的有限条公理的合取。由可靠性和完备性可得

Q⊢HM,w⟺⊨AQ→HM,w.Q\vdash H_{M,w} \quad\Longleftrightarrow\quad \models A_Q\rightarrow H_{M,w}.

因此,如果存在逻辑有效性的判定算法,就能用它判定停机问题,而这是不可能的。这一现代归约并非图灵最初采用的论述方式,但它明确揭示了:判定纯粹逻辑有效性的能力为何会超出计算的极限。

半判定、证明搜索与答案的不对称性

不存在判定程序,并不意味着无法以系统的方式识别有效的一阶语句。在标准的有效证明演算中,检查一个有限序列是否为形式正确的证明,是可以机械完成的。所有有限字符串都可以枚举出来,其中构成合法证明的字符串也可以识别。因此,程序可以枚举出所有逻辑定理。

对于输入语句 φ\varphi,程序在这一枚举过程中不断搜索,直到找到 φ\varphi 的证明。如果 φ\varphi 有效,完备性保证搜索最终会成功。如果 φ\varphi 无效,可靠性保证不可能找到证明,因此搜索会永远运行下去。所以,有效性是可计算枚举的,也称递归可枚举的或半可判定的。识别程序保证会在肯定实例上终止,而判定程序则必须在肯定实例和否定实例上都终止。

这种不对称性有一个确切的推论。如果一个集合及其补集都是可计算枚举集,那么这个集合就是可判定的:只需并行运行两个识别程序,交替执行它们的步骤,直到其中一个接受输入。最终必有且仅有一个程序会接受。由于一阶逻辑的有效性是可计算枚举的,却不可判定,因此无效性不可能也是可计算枚举的。等价地,不受限制的一阶逻辑可满足性不是可计算枚举的,而不可满足性则是。

搜索有限反模型并不能消除这一困难。对于有限的关系词汇表,可以穷尽检查具有任意给定有限论域的所有结构。找到一个使 φ\varphi 为假的结构,就能确认它无效。但并非每个无效语句都有有限反模型。一阶语句可以施加只有在无限论域中才能实现的条件。

例如,使用一元函数符号 ff,语句

∀x∀y (f(x)=f(y)→x=y)  ∧  ∃z∀x f(x)≠z\forall x\forall y\,(f(x)=f(y)\rightarrow x=y) \;\land\; \exists z\forall x\,f(x)\ne z

表示 ff 是单射但不是满射。任何有限论域上都不存在这样的函数,而自然数上则存在,例如 f(n)=n+1f(n)=n+1。因此,该语句的否定在这一符号表下的每个有限结构中都为真,却并非逻辑有效。仅限于有限反模型的搜索,永远无法证实这种无效性。

这一区别也有定量的表现。采用通常的有效语法编码时,不存在一个仅依赖语句长度的可计算界限,能够为每个有效语句的最短证明长度给出上界。如果存在这样的界限,程序就可以检查不超过该长度的所有候选证明;如果其中没有任何一个能证明该语句,就将其拒绝。这样便能判定有效性。因此,不可判定性不仅限制了判定一个语句是否为定理的可能性,也限制了预先为所需的证明搜索给出统一界限的可能性。

与哥德尔不完备定理的关系

判定问题的否定解答与哥德尔不完备定理密切相关,但这些结果回答的是不同的问题。判定问题关注的是,是否存在一种算法,能够判定逻辑有效性或一个语句是否为定理。不完备性关注的则是,某个特定的公理化理论,能否证明足够多的、关于其预期数学研究对象的陈述。

哥德尔第一不完备定理发表于1931年,适用于包含足够算术内容、相容且可有效公理化的理论。该定理的标准加强形式表明,这样的理论无法判定其语言中的每一个语句:存在一个语句 γ\gamma,使得 γ\gamma 和 ¬γ\neg\gamma 都不可证。这里的“判定”是指理论能够证明某个语句或其否定,而不是指由外部算法判定某个语句是否属于该理论的定理集。

这两种概念并不等价。一个理论可能不完备,但其定理集仍然是可判定的。带有等号、但不含任何非逻辑符号的语言中的空理论就是一个例子:它的逻辑后承是可判定的,但它既不能证明“恰好存在一个对象”这一断言,也不能证明其否定。反过来,仅仅拥有大量公理,并不能产生有效的判定程序;公理的给定方式以及由此得到的理论的强度,都至关重要。

不过,两者之间仍然存在一项重要联系。如果一个可有效公理化的理论是相容的,并且在语法上完备,那么某个语句是否为该理论的定理就是可判定的。给定语句 φ\varphi,只需枚举证明,直到 φ\varphi 或 ¬φ\neg\varphi 出现。完备性保证其中一个必定出现,而相容性保证两者不会同时出现。因此,一个完备且有效的公理化系统,会自动为其语言中的语句提供判定程序。

算术也从相反方向搭起了桥梁。如果一个理论足够强,能够验证任意有限计算,那么其定理集就能够编码停机问题。因此,若有算法能够判定这个定理集,它也就能判定一个不可判定的计算问题。更强的结果表明,罗宾逊算术是本质不可判定的:它的每一个相容且可有效公理化的扩张,仍然都是不可判定的。这类结果将可计算性的界限,与无法通过有效增添公理使算术完备这一事实联系起来。

哥德尔关于一阶逻辑的完备性定理,与算术的不完备性并不矛盾。逻辑完备性是说,凡是在给定一阶公理的所有模型中都为真的语句,都可以从这些公理形式地推导出来。算术不完备性则是说,一个有效公理化的理论无法涵盖预期自然数结构中的全部真理。该理论的公理具有不同的模型,而这些模型对理论无法判定的语句会有不同的真值。因此,在比较这些定理时,必须区分所有结构、给定公理的模型,以及某一个预期结构。

可判定片段与相关问题

不受限制的一阶逻辑有效性不可判定,但仍有广泛的可判定领域。最简单的对照是命题逻辑:一个含有 nn 个命题变元的公式有 2n2^n 种真值赋值,因此穷举求值总能终止。更高效的方法往往能避免逐一显式检查所有赋值。可能产生的计算开销属于计算复杂性的研究范畴;它关注的是一个可计算问题需要多少时间或空间,而不是这个问题究竟是否可计算。

一元一阶逻辑是另一个经典的可判定情形。在一种标准形式中,其非逻辑符号仅包含一元谓词和常元,允许使用等号,但不包含元数大于零的函数符号。一元谓词描述单个对象的性质,而不直接编码不同对象之间的任意关系。谓词的真值组合只有有限多种,可以通过分析满足各类组合的对象数量来分析句子。由此,可以对需要考察的结构给出可有效计算的界限。

伯奈斯—申芬克尔类施加了另一种限制。这类句子由一组存在量词后接一组全称量词构成,

∃x1⋯∃xm ∀y1⋯∀yn θ,\exists x_1\cdots\exists x_m\, \forall y_1\cdots\forall y_n\,\theta,

其中 θ\theta 不含量词,且句子中没有元数大于零的函数符号。就可满足性而言,存在变元的见证可以用常元表示。由于没有函数,就不会生成无穷嵌套的新项,因此可以将问题归约为有限个不含变元的实例。这一类通常称为有效命题逻辑。

尽管不受限制的逻辑不可判定,某些特定数学理论仍有判定程序。普雷斯伯格算术描述带有加法、但不允许任意使用乘法的自然数,其可判定性于1929年得到证明。相比之下,同时包含加法和乘法的算术能够表达证明不可判定性所需的计算编码。这一区别表明,两种各自简单的常见运算结合起来,可以产生强大得多的表达能力。

阿尔弗雷德·塔斯基为实闭域的一阶理论建立了判定程序。该程序利用量词消去,将涉及多项式方程和不等式的公式转化为等价的无量词条件。一个简单的例子是

∃x (x2+a=0)⟺a≤0.\exists x\,(x^2+a=0) \quad\Longleftrightarrow\quad a\leq 0.

这是关于某个特定代数理论的定理,而不是针对任意关系符号的任意解释的判定程序。

改变所允许的结构,可能会产生实质上不同的问题。1950年,鲍里斯·特拉赫滕布罗特证明,对于表达能力足够强的关系符号集,一阶逻辑的有限可满足性是不可判定的。尽管如此,有限可满足性仍然是可计算枚举的,因为可以枚举并检验有限结构。这与不受限制的可满足性形成对照,表明语义的具体选择不仅影响可判定性,也影响一个问题的哪一方能够被有效识别。

自动推理与这一结果的适用范围

判定问题为自动定理证明划定了一个明确的界限:不存在一个程序,能够对所有不加限制的一阶语句都作出正确判定,并且总能终止。但这并不妨碍程序找到困难的证明、驳斥不一致的假设、发现有限模型,或对范围广泛的受限类别作出判定。成功的系统正是利用了这些可能性。

一项重要进展是 J. 艾伦·罗宾逊于1965年提出的归结原理。基于归结的定理证明器通常先将待证定理取否定,再把结果转换为适当的子句形式,然后搜索矛盾。搜索过程依赖于合一,即寻找能使符号表达式变得相同的代换。例如,P(x,a)P(x,a) 和 P(b,y)P(b,y) 可以通过将 xx 替换为 bb、将 yy 替换为 aa 来合一。

归结对一阶逻辑具有反驳完备性:采用适当的穷尽搜索策略时,不可满足的子句集最终会导出表示矛盾的空子句。但如果输入是可满足的,搜索就未必会终止。这正是半判定与判定之间的区别在运行过程中的体现。实际应用中对搜索时间或内存的限制还会引入另一种结果——未能得出答案;不能将这种结果误认为可满足性的证明。

可满足性模理论系统采用了另一种方法。这类系统将命题推理与针对特定背景理论的处理过程相结合;这些理论包括线性算术、固定位宽的位向量、数组,以及带未解释函数的等式理论等。其中一些组合与片段是可判定的,另一些则需要采用不完备的策略,或进行没有预定终止界限的量词推理。因此,一个系统在逻辑上能提供何种保证,取决于它所支持的语言和理论,而非“自动求解器”这一笼统称谓。

在形式验证中,检查一个给定的有限状态系统与分析具有无界存储的任意程序之间,也存在同样的界限。有限状态系统的可达性问题可以通过穷尽遍历状态来解决,而且这一过程必然终止,尽管状态空间可能大到难以处理。一般的程序终止性问题或不受限制的语义正确性问题则可以编码停机问题。抽象、不变式和受限的程序语言,使许多有用的验证任务变得可处理,但并未提供一种通用的解决方法。

这一定理也区分了发现证明与检查证明。即使不存在能够始终判定某个证明是否存在的算法,有限的形式证明仍然可以由算法检查。证明助手和能够输出证明的定理证明器利用的正是这一差别:可能十分复杂的搜索或由人引导的推理产生一份证明凭证,再由一个相对小巧的检查组件核验具体的推导过程。不可判定性结果所针对的是一种总能终止并作出正确判定的通用方法,而不是对已经给出的证明进行机械核验。