判定问题与语言, 递归可枚举，非递归可枚举，对角语言（理论计算机基础复习六)

A decision problem requires checking if an input (string) has some property. Thus, a decision problem is a function from strings to boolean.一个判定问题要求检查输入字符串是否具有某种性质。因此判定问题可看作从字符串到布尔值的函数。A decision problem is represented as a formal language consisting of those strings (inputs) on which the answer is yes.一个判定问题可表示为一个形式语言该语言恰好由那些答案为yes 的输入字符串组成满足条件的字符串Recursive Enumerability 递归可枚举性A Turing Machine on input w either accepts (and halts), or rejects (and halts), or never halts.图灵机在输入 w 上要么接受并停机要么拒绝并停机要么永不停机。我们叫w 是具有递归可枚举性质的或者叫w 是图灵机可识别的。The language of a Turing Machine M, denoted as L(M), is the set of all strings w on which M accepts.图灵机 M 的语言记作 L(M)它是所有会被 M 接受的字符串 w 的集合。A language L is recursively enumerable or Turing recognizable if there is a Turing Machine M such that L(M) L.若存在图灵机 M 使得 L(M) L则语言 L 称为递归可枚举或图灵可识别。Decidability 可判定性A language L is decidable if there is a Turing machine M such that L(M) L andM halts on every input.若存在图灵机 M使得L(M) L 且 M 对每个输入都停机则语言 L 是可判定的。Thus, if L is decidable then L is recursively enumerable.因此若 L 可判定则 L 一定是递归可枚举的。Undecidability 不可判定性Definition: A language L is undecidable if L is not decidable. Thus, there is no Turing machine M that halts on every input and L(M) L.定义若语言 L 不是可判定的则称 L 不可判定。因此不存在图灵机 M 既对每个输入都停机又满足 L(M) L。This means either L is not recursively enumerable, i.e. there is no Turing machine M such that L(M) L这意味着要么 L 不是递归可枚举的即不存在图灵机 M 使得 L(M) LL is recursively enumerable but not decidable, i.e. for any Turing machine M with L(M) L, M does not halt on some inputs.L 是递归可枚举但不可判定也就是对任何满足 L(M) L 的图灵机 MM 在某些输入上不停止。Machines as Strings 把机器编码成字符串For the rest of this lecture, let us fix theinput alphabet to be {0,1}; a string over any alphabet can be encoded in binary.在本讲其余部分固定输入字母表为 {0,1}任意字母表上的字符串都可编码为二进制。Any Turing Machine or program M can itself be encoded as a binary string. Moreover, every binary string can be thought of as encoding a TM or program (if not in the correct format, it is considered the encoding of a default TM).任意图灵机或程序 M 本身都可编码为二进制串。此外每个二进制串都可视作某个 TM 或程序的编码若格式不合法则视为某个默认 TM 的编码。We will consider decision problems (languages) whose inputs are Turing machines (encoded as binary strings).我们将考虑这类判定问题语言其输入本身是图灵机以二进制串编码。The Diagonal Language 对角语言Definition: L_d { M | M ∉ L(M) }.定义L_d { M | M ∉ L(M) }。Thus, L_d is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input.因此L_d 是这样一类图灵机程序M 的集合当把 M 自身作为输入时M 不会停机并接受核心逻辑分析输入的特殊性在图灵机理论中程序 M 本身可以被编码成字符串。因此我们可以把程序 M 的代码作为输入数据喂给 M 自己去运行。判定标准如果 M 运行自己的代码后进入了“接受”状态那么 M 就不属于 L_d。如果 M 运行自己的代码后结果是“拒绝”或者“死循环不停机”那么 M 就属于 L_d。为什么叫“对角”想象一个表格行和列都是所有的图灵机。第 i 行第 j 列表示“图灵机 i 是否接受 字符串 j”。当 i j 时就构成了表格的对角线。L_d 关注的就是这些对角线上的元素。额外的例子想象有一类特殊的程序员他们的工作是测试程序。有些程序员很自恋他们写的程序在测试自己的代码时总是显示“通过接受”。有些程序员很严谨或很奇怪他们写的程序在测试自己的代码时总是显示“报错拒绝”或者干脆“卡死死循环”。对角语言 L_d 就是“所有用自己的程序测试自己的程序会报错或卡死的程序”的集合。A non-Recursively Enumerable Language 非递归可枚举语言L_dProposition: L_d is not recursively enumerable.命题L_d 不是递归可枚举的。Proof.Recall that,回忆如下Inputs are strings over {0,1}.输入是 {0,1} 上的字符串。Every Turing Machine can be described by a binary string, and every binary string can be viewed as a Turing Machine.每个图灵机都可由某个二进制串描述每个二进制串也都可看作某个图灵机。In what follows, we denote the i-th binary string in lexicographic order as the number i. Thus we can say j ∈ L(i), meaning that the Turing machine corresponding to the i-th binary string accepts the j-th binary string.下文把按字典序第 i 个二进制串记作编号 i。于是可写 j ∈ L(i)表示「第 i 个二进制串所对应的图灵机」接受「第 j 个二进制串」。Completing the proof补全证明Proof (contd).证明续We can organize all programs and inputs as an infinite matrix, where the (i, j)-th entry is Y if and only if j ∈ L(i).把所有程序与所有输入排成一张无穷矩阵第 (i, j) 格为 Y当且仅当 j ∈ L(i)。Suppose L_d is recognized by a Turing machine that is the j-th binary string, i.e. L_d L(j).假设 L_d 能被「第 j 个二进制串所对应的」某台图灵机识别即 L_d L(j)。But j ∈ L_d iff j ∉ L(j)!但 j ∈ L_d 当且仅当 j ∉ L(j)图中矩阵列为输入 1, 2, 3, …行为机器 1, 2, 3, …对角线 (i, i) 用红框标出其余格为 Y/N。In the figure: columns are inputs 1, 2, 3, …; rows are TMs 1, 2, 3, …; diagonal (i, i) is boxed in red; entries are Y/N.Acceptor for L_d?L_d 的判定器接受器Consider the following program:考虑下面程序On input i输入为 i 时Run program i on i运行程序 i 在输入 i 上Output “yes” if i does not accept i若 i 不接受 i则输出 “yes”Output “no” if i accepts i若 i 接受 i则输出 “no”Does the above program recognize L_d?No, because it may never output “yes” if i does not halt on i.上面的程序是否识别 L_d不是因为如果 i 在 i 上不停机它可能永远输出不了 “yes”。、Recursively Enumerable but not Decidable 递归可枚举但不可判定L_d is not recursively enumerable, and therefore not decidable. Are there languages that are recursively enumerable but not decidable?L_d 不是递归可枚举的因而也不是可判定的。是否存在「递归可枚举但不可判定」的语言Yes: A_TM { ⟨M, w⟩ | M is a TM and M accepts w }.有A_TM { ⟨M, w⟩ | M 是 TM 且 M 接受 w }。The Universal Language 通用语言接受问题Proposition: A_TM is recursively enumerable but not decidable.命题A_TM 是递归可枚举的可识别但不是可判定的。Proof: A_TM is r.e.证明A_TM 是递归可枚举的可识别有3种结果 停机接受停机拒绝陷入循环。On input ⟨M, w⟩输入 ⟨M, w⟩Run M on input w在输入 w 上运行 MOutput “yes” if M accepts w若 M 接受 w则输出 “yes”Output “no” if M rejects w若 M 拒绝 w则输出 “no”注意若 M 在 w 上不停机则该过程也不会停因此这给出的是识别器而非判定器。Note: if M loops on w, this procedure does not halt; hence this is a recognizer, not a decider.Proof: A_TM is not decidable证明A_TM 不可判定。Suppose (for contradiction) A_TM is decidable. Then there is a TM M that always halts and L(M) A_TM. Consider TM D as follows:为证矛盾设 A_TM 可判定则存在总停机的 TM M 且 L(M) A_TM。(Atm 可判定意味着存在一个图灵机比如U它都能在有限时间内告诉你结果接受或拒绝绝对不会死循环。)通过将问题转化归约为我们之前学过的“对角语言L d L_dLd​”来制造矛盾定义 TM D 如下On input i输入为 i 时Run M on input ⟨i, i⟩ ⟨i, i⟩ 意思是待测试的机器机器的输入数据在输入 ⟨i, i⟩ 上运行 MOutput “yes” if i rejects i若 i 拒绝 i则输出 “yes”Output “no” if i accepts i若 i 接受 i则输出 “no”Observe that L(D) L_d! But L_d is not r.e., which is a contradiction.可见 L(D) L_d但 L_d 不是递归可枚举的矛盾。所有最初的假设——Atm可判定是错误的 即Atm是不可判定。Languages ⊃ Recursively Enumerable ⊃ Decidable ⊃ Regular.语言类 ⊃ 递归可枚举 ⊃ 可判定 ⊃ 正则。Outside Recursively Enumerable (still languages): examples include L_d and ĀTM (complement of A_TM).在「仍为语言、但不属于递归可枚举」的区域例如 L_d 与 ĀTMA_TM 的补语言。Inside Recursively Enumerable but not Decidable: example A_TM.递归可枚举但不可判定例如 A_TM。Inside Decidable but not Regular: example L_0ⁿ1ⁿ.可判定但不正则例如 L_0ⁿ1ⁿ。Innermost: Regular.最内层正则语言类。