无解问题

语言与计算理论导引无解问题陶晓鹏Copyright20031第五部分无解问题和可计算函数专用计算模型（比如下推自动机）与通用计算模型（比如图林机）的区别是对于前者，我们必须考虑抽象机本身的局限和解决某个特定问题的算法（或经过修改）能不能容纳进这个被严格限制的计算模型中，对于后者，我们不用考虑抽象机，只要关心这个问题是否能够被解决。因为根据Church-Turing论题，任何一个算法都能在图林机上编码处理。而任何不能在图林机上解决的问题都称为无解问题（或不可解）。我们将看到，对于图林机的计算能力，存在许多难度太大而无法求解的问题。在第5部分，我们从利用对角线参数法构造一个不能被图林机识别的语言开始讨论无解问题。在第12章，我们考虑一个通用的方法，它将一个语言，或者一个判定问题规约到另一个语言，或另一个判定问题。这将使我们发现一大类无解问题，包括图林机处理自身的问题，和其他一些能够用通用计算术语表达的问题。讨论完无解问题后，我们回到可解问题的讨论上，并且尝试着独立于图林机来刻画这些问题。在第13章，我们证明了能够被图林机计算的函数恰好是一些基本函数，施加三种操作得到的函数，这三种操作是组合（composition）、原始递归（primitiverecursion）、无界限最小化（unboundedminimalization）。最后，我们提到可计算性的其他一些形式化的方法。我们将发现，概括而言，其他的各个模型等价于图林机模型，这样的等价性进一步说明了Church-Turing论题的合理性。问题：注意区分可计算性、有解问题、NP问题这些概念的区别和联系。12无解问题12.1一个无解的判定问题图林机是一个通用的计算模型，它能够解决的问题之一是判定问题。比如，下面的判定问题，给定字符串x{a,b}*，x是否属于回文语言pal？能够被图9-2所示的图林机解决。这个问题的实例（instance）是某个特别的字符串，比如abbaba，把这个字符串输入到图林机中，图林机停机时的结果是1，则表示回答“是”，如果结果是0，则表示回答“否”（对于abbaba，回答是“否”）。对于能够被图林机解决的更复杂的问题，我们需要基于抽象机的输入字母表对实例进行编码。判定问题，给定一个上下文无关文法G，L(G)是否是空集？的一个实例是一个特定的CFGG。在某个固定的字母表上，比如{0,1}，对G的编码包括G的终结符和非终结符的编码，以及G的产生式的编码。在这种情况下，有些输入字符串不能表示这个问题的一个合法实例，因此解决这个问题的预备步骤是确定当前输入字符串是否是一个实例的编码。概括而言，一个图林机T解决一个判定问题P的方法如下，图林机T获得输入字符串x，然后确定x是否表示了P的一个实例，如果是，则确定x是否是一个“肯定实例”（yes-instance）。简洁而言，T通过识别由P中肯定实例的编码组成的语言来解决判定问题P。一个图林机能够解决一个判定问题是因为表示肯定实例的字符串组成的语言是递归语言（或能够被图林机识别的语言）。定义（无解问题）非正式地，如果没有一个通用的算法判定问题的每个实例，那么我们说这个判定问题是无解的。定义（无解问题2）根据Church-Turing论题，如果判定问题的肯定实例的编码（依据某个语言与计算理论导引无解问题陶晓鹏Copyright20032合理的编码函数）组成的语言不是递归的，那么这个判定问题是无解的。特别地，任何一个非递归语言L直接对应一个无解的判定问题，即这个语言的成员资格判定问题：给定字符串x，x是否是L的元素？下面是我们最先给出的非递归语言之一，SA={w{0,1}*|存在某个图林机T，w=e(T)，且T接受w}SA含义是“Self-Accepting”（自接受）。SA中的字符串表示图林机T接受它自身的编码e(T)（e是预先定义的编码函数）。因此SA是下面判定问题，自接受（Self-accepting），的肯定实例的编码组成的集合（或语言），给定一个图林机T，它是否接受它自身的编码e(T)？我们可以把这个问题作为第一个正是给出的无解判定问题。一个技术上的观点值得在这里讨论。从语言SA开始，我们可以按照如下方法得到一个无解问题：给定一个0和1组成的字符串x，问x是否是SA的一个元素？（换句话说，给定一个字符串x，x是否表示了一个接受它自身的图林机？）这是一个典型的关于集合SA的成员资格判定问题，它听起来与自接受问题有些不同，似乎更难了，这是因为在判断x表示的图林机是否接受x之前，我们先要判断x是否是一个图林机的合法的编码。非正式场合下，我们不区别这两个问题。原因是只要我们对任意的判定问题选择了一个编码函数，我们总是能够发现解码的算法，从而确定一个字符串是否代表了问题的一个合法实例，如果是，则重构这个实例。明确涉及字符串的问题的表述听起来涉及到更多的工作，但是这个额外的工作是图林机的输入字符串需要被编码这样的事实所必须的。在讨论可解性和无解性的环境中，这个额外的关于编码解码的工作可以忽略不计。SA的成员资格问题是无解问题，因为自接受问题本身的难度，而与采用的编码解码函数的难度无关。值得注意的是，一个问题的无解并不意味着这个问题的所有实例都是无法解决的，比如，显然存在很多图林机T，我们能够很容易地判定T是否接受e(T)。导致自接受问题成为无解问题的原因是找不到一个通用的算法能够对问题的每个实例作出正确的回答。12.2问题规约和停机问题我们利用对角线参数法显示了自接受问题是无解的。现在，我们发现了一个无解问题，其他无解问题将比较容易发现。自接受问题的主要用途是展示许多其他问题的无解性，那些问题具有更直观的意义。如果我们不能解决一个给定图林机T是否能够接受一个特定的字符串e(T)这样的问题，显然，我们更无法解决更通用的问题，即递归可枚举语言的成员资格判定问题。这是最著名的无解判定问题。根据图林机接受语言的方式，这个问题被称为停机问题。停机问题：给定一个图林机T和一个字符串w，问wL(T)？值得再次提醒的是，处理这个问题的明显的方法（即将w输入T，观察T的运行情况）是无解的，因为这个方法只有在T停机或崩溃时给出答案，而出现无限循环时则无解。停机问题的一个实例包含一个图林机T和一个字符串w，使用编码函数e，停机问题的实例(T,w)，可以表示成字符串e(T)e(w)，我们考虑下面的语言H={e(T)e(w)|wL(T)}因此说停机问题是无解的相当于说语言H是非递归的，从前面的讨论这也是一个很直观的结论。但是我们将引入一个通用技术来更系统地证明这个结论，这个通用技术从此以后将经常用到，它的思想是将一个问题规约为另一个问题。这是一个我们熟悉的思想，我们常常非正式地使用这个方法。当我们说问题P1能够规约到问题P2，通常的含义是问题P2的解决能够保证我们解决问题P1，或通俗地讲，问题P1没有问题P2难，或者说（逆否命题）如果问题P1很难，那语言与计算理论导引无解问题陶晓鹏Copyright20033么问题P2也很难。尽管我们可以很自由地在非正式的水平上考虑判定问题，但图林机必须直接处理这些问题对应的语言。既然图林机是我们正式的计算模型，我们首先给出一个语言被规约到另一个语言的定义，然后我们能够根据问题本身重新表述这个定义。定义12.1（一个语言规约到另一个语言）如果L1和L2分别是字母表1和2上的语言，则我们说L1可以规约到L2（记为L1L2），如果满足下面的条件：存在一个（图林机）可计算函数f:1*2*，任给x1*，都有，xL1当且仅当f(x)L2通常这种类型的规约称为多对一（many-one）规约，符号也常常写成m。本节我们不再引入其他类型的规约，因此有些记号可以写成简化的形式。问题：1）如果将上面的规约函数修改成f:L1L2，还会保持规约函数的性质吗？2）显然f除了可以是多对一，还可以是一对多，或一对一，它们会影响规约函数的性质吗？这里的思想是，如果语言L1L2，那么能够解决L2的成员资格判定问题就意味着能够解决L1的相同问题。这也正是语言规约的定义告诉我们的。如果我们有一个字符串x1*，并且要判定是否xL1，则我们可以用间接的方法，先计算f(x)，然后判定是否f(x)L2。由于它们满足规约的性质，因此f(x)L2的判定结果能够告诉我们xL1的判定结果，即确定L1的成员资格没有确定L2的成员资格难，从这个意义上讲，唯一要作的附加工作是计算函数f。正如前面提到的，我们可以将上面的定义翻译成正面的命题，即一旦我们有了判定L2的成员资格的方法，我们也有了判定L1的成员资格的方法；或者翻译成反面的命题，如果很难判定L1的成员资格，那么也很难判定L2的成员资格。本章，我们更感兴趣后面的反面命题，因为我们讨论的内容是无解问题。此处，我们给出判定无解问题的主要方法的陈述，本章的定义用于这个方法之中。定理12.1如果L1和L2分别是字母表1和2上的语言，并且L1L2，那么如果L2是递归的，则L1也是递归的（逆否命题，如果L1不是递归的，则L2也不是递归的）。证明：根据假设L1L2，那么存在将L1规约到L2的函数f:1*2*，且设f可以被图林机T计算，换句话说，任给x1*，都有(q0,x)*(h,f(x))现在假设L2是递归的，则存在一个识别（或判定）L2的图林机T2。我们能够构造识别L1的图林机T1＝TT2。它的含义是当输入字符串x，T1首先调用T计算字符串f(x)，输出结果是f(x)，然后T1调用T2处理f(x)，输出结果是1或0（依赖于f(x)是否属于L2）。既然f(x)L2当且仅当xL1，因此组合图林机T1在xL1时输出1，xL1时输出0，因此T1是计算L1的特征函数的图林机。因此L1是递归语言。当我们使用定义12.1时，我们把分别在字母表1和1上的字符串看成L1和L2上的成员资格问题的一个实例。如果函数f是L1到L2的规约函数，那么我们有了一个办法，从有关L1的问题的一个实例出发，得到有关L2的问题的一个实例，而且这两个实例的答案是一致的，即如果x是第一个问题的肯定实例，当且仅当f(x)是第二个问题的肯定实例。这意味着第一个判定问题（L1的成员资格问题）被规约到第二个问题（L2的成员资格问题）。现在我们可以用这个想法去重新说明什么是一个判定问题P1规约到另一个问题P2（前面我们定义了语言的规约，此处定义问题的规约）。定义12.1a（一个判定问题规约到另一个问题）如果P1和P2是判定问题，我们说P1可以语言与计算理论导引无解问题陶晓鹏Copyright20034规约到P2（记为P1P2），如果满足下面的条件：存在一个算法过程F，任给P1的一个实例I1，能够找到P2的一个实例F(I1)，而且I1是P1的肯定实例当且仅当F(I1)是P2的肯定实例。命题P1P2的通俗解释是，P1没有P2困难，如果我们想判定P1的一个实例I1，我们可以先找到P2对应的实例F(I1)，然后判定F(I1)。对这两个实例的答案是一致的。定义12.1a的陈述没有定义12.1更形式化，我们在12.1a中谈论的是实例和算法，而不是定义12.1中谈论的字符串和图林机。在初始例子中，判定问题是L1和L2的成员资格问题，而问题的实例是字符串，因此，我们只要把术语“算法过程”想象成“图林机”，两个定义对初始例子没有区别。但更广泛而言，问题P1和P2的实例可以是其他形式的对象，比如数字、集合、图形、图林机等等，而且P1的实例的形式可以不同于P2的实例的形式。为了在所有这些问题上使用图林机，我们必须把这些实例编码成字符串，一旦我们有了合适的编码函数，容易看到两个定义之间的密切关系。如果e1是P1在1上的编码函数，e2是P2在2上的编码函数，那么我们考虑分别由P1的肯定实例的编码和P2的肯定实例的编码组成的语言L1和L2。P1可以通过F规约到P2，L1可以通过f规约到L2。下面的图总结了上面的讨论，上面一层是问题实例，下面一层是语言的字符串，连接两个层次的函数是编码函数e1和e2。I1