计算理论与算法分析设计课件：不可判定性

CH5不可判定性

2024/6/302

of158丘奇-图灵论题在所有输入上都停机的TM作为“算法”的直觉化概念。根据丘奇-图灵论题，不能用TM完成的计算任务，是不可能的,没有希望的。5.1丘奇-图灵论题2024/6/303

of158丘奇-图灵论题是论题，不是定理，因为它不是数学结果：它只断言某个非形式化概念（算法）对应于某个数学对象(TM）。因为不是数学命题，所以丘奇-图灵论题不能被证明。不过在理论上有可能在未来某一天丘奇-图灵论题被证伪，假设有人提出另一种计算模型，公认它是有说服力的和合理的，并且证明它能完成用TM不能完成的计算。没有人认为这是可能的。5.1丘奇-图灵论题2024/6/304

of158在第一章里论证过，若利用字符串去表示语言则不能表示出所有语言：在任何字母表上只有可数个字符串，却有不可数个语言。有穷自动机、下推自动机、上下文无关文法和TM都是可用来规定语言的有穷对象的例子，并且它们自身可用字符串来描述。相应地在任何字母表上只有可数多个递归和递归可枚举语言。所以，虽然我们尽量扩充计算机的能力，但是从根本上说，在所有可能的语言里只有无穷小的部分可用计算机去半判定或判定。5.1丘奇-图灵论题2024/6/305

of158在前几章里发现过非正则语言；在本章我们同样要发现非递归语言。不过有两点主要区别。首先，这些新的否定性结果不仅仅是暂时的挫折，等着下一章定义更强的计算装置来克服：根据丘奇-图灵论题，不能用TM完成的计算任务，是不可能的,没有希望的。其次用来证明语言是非递归的方法不得不有别于为发掘上下文无关文法和有穷自动机的弱点而用过的“泵”定理。5.1丘奇-图灵论题2024/6/306

of158我们认为TM的形式化是可用来写程序的编程语言。然后用这种语言写的程序被通用TM—即用同样语言写的另一段程序—解释执行

。5.2通用TM2024/6/307

of1585.2通用TM2024/6/308

of1585.2通用TM

通过这种方法，任意的TM都可被表示出来。我们用同样方法表示TM的字母表里的字符串。任何字符串w*都有唯一的表示，即它的符号的表示的并置，也记作“w”。2024/6/309

of1585.2通用TM2024/6/3010

of158

i＝2和j＝3

2i≥32j≥3＋2的最小整数。2024/6/3011

of1582024/6/3012

of1582024/6/3013

of158

现在我们准备就绪讨论通用Turing机U，它用其他机器的编码作为程序来指导它的操作。直观上，U收到两个自变量，分别是机器M的描述“M”和输入字符串w的描述“w”。我们希望U具有下列性质：U在输入“M”“w”上停机当且仅当M在输入w上停机。即

U(“M”“w”)=“M(w)”5.2通用TM2024/6/3014

of1585.2通用TM2024/6/3015

of1585.2通用TM2024/6/3016

of1585.2通用TM2024/6/3017

of158

假设你用喜欢的编程语言写了完成下列不寻常操作的程序：它收到用同样语言写的程序P和这个程序的输X作为输入。通过某些聪明的分析，你的程序总是正确地判定在输入X上程序P是否停机（若P停机则它返回“是”），或者P是否死循环（若P死循环则它返回“否”）。你把这段程序命名为halts(P,X)。5.3停机问题2024/6/3018

of158这是最有价值的程序。它发现使得其他程序在某些输入上死循环的所有微妙的编程错误。你可用它完成许多不寻常的事情。这里是一个有点微妙的例子：你可用它写用不祥的名字diagonal(X)命名的另一段程序：

diagonal(X)

a:ifhalts(X,X)thengotoaelsehalt如果你的halts程序断定程序X用它自身X作为输入时X停机，那么diagonal(X)死循环；否则它停机。5.3停机问题2024/6/3019

of158现在出现无法回答的问题:diagonal(diagonal)是否停机?halts(P,X):正确地判定在输入X上程序P是否停机。它停机当且仅当对halts(diagonal,diagonal)的调用返回“否”；换句话说，它停机当且仅当它不停机。这是矛盾，我们必须得出结论说把我们领向此路的唯一假设是假的，程序halts（P,X)其实并不存在。也就是说，没有程序，没有算法可解决假设halts解决的问题：辨别任意的程序是停机还是死循环。diagonal(X)

a:ifhalts(X,X)thengotoaelsehalt如果你的halts程序断定程序X用它自身X作为输入时X停机，那么diagonal(X)死循环；否则它停机。2024/6/3020

of158H={“M”“w”：Turing机M在输入w上停机｝首先注意H是递归可枚举的：它恰好是用上一节里的通用Turing机半判定的语言。确实，在输入“M”“w”上，恰好当输入属于H时U才停机。下面证明H不是递归的。首先，如果假设H是递归的，那么H1={“M”:Turing机M在输入字符串“M”上停机}也是递归的。非递归语言2024/6/3021

of158非递归语言证明H1={“M”:Turing机M在输入字符串“M”上停机}也