ITOC chapter5 可归约性

5 Reducibility 可归约性

如果问题A可归约为问题B,那么只要解决了问题B,就可以解决问题A了,即A⟵B。

例如要在城市中认路,我们可以通过找到一张地图来解决。A就是认路问题,B就是得到地图问题。

又例如,求矩形面积可以归约为求矩形的宽和高的问题。

当A归约到B时,解A不可能比解B更难,所以:
如果B是可判定的,那么A也是可判定的
如果A是不可判定的,那么B也是不可判定的

所以要证明一个问题B不可解,可以先证明另一个问题A不可解,然后将A归约到B,证明完毕。

5.1 Undecidable Problems from Language Theory 语言理论中的不可判定问题

ATM不可判定为基础,证明某些语言不可判定的方法(套路):

假设另一语言可判定,令其判定机为R⟶用R构造出ATM的decider S(关键)⟶ATM可判定
矛盾出现,假设不成立,证毕。

停机问题

HALTTM={⟨M,w⟩| M时图灵机,M对输入w停机 }.即确定图灵机对给定的输入是否停机。

证明HALTTM式不可判定的

思路:假设判定HALTTM的机器为R,那么我们可以构造ATM的判定机:如果R返回不停机,那么拒绝,如果R返回停机,那么就模拟一次,根据返回结果来输出接受/拒绝。这样ATM就是可判定的了,但ATM是不可判定问题,所以R不存在。

TM空性质测试

ETM={⟨M⟩| M is a TM and L(M) = ∅} .即判断图灵机是否不接受任何串。

构造M1 = “On input x:
1. If x≠w, reject.
2. If x=w, run M on input w and accept if M does.”

构造S = “On input <M,w>, an encoding of a TM M and a string w:
1. Use the sescription on M and w to construct the TM M1 just described.
2. Run R on input M1.
3. If R accepts, reject; if R rejects, accept.”

对于输入w,如果M接受w,那么在M1会返回接受,M就非空,R就会拒绝,S就会接受。

如果M不接受w,那么M1就是空的,R就会接受,S就会拒绝。所以S就是ATM的判定机,矛盾!

REGULARTM不可判定

REGULARTM={⟨M⟩| M is a TM and L(M) is a regular language}.即判断一个图灵机是否识别某个正则语言。

构造S = “On input <M,w>, where M is a TM and w is string:
1. 构造M2.
M2 = “On input x:If x has the form 0^n1^n accept.
If x does not have this form, run M on input w and accept If M accepts w.”

2. Run R on input ⟨M2⟩.
3. If R accepts, accept; if R rejects, reject.”

如果M接受w,那么M2接受,R接受,S接受。如果M不接受,M2接受则R不接受,S不接受,M2不接受则R不接受,S不接受。

EQTM不可判定

QTM={⟨M1,M2⟩|M1 and M2 are TMs and L(M1)=L(M2)}.即判断俩图灵机是否识别同一种语言。

这里以ETM为证明基础:EQTM⟵ETM.

S = “On input <M>, where M is a TM:
1. Run R on input ⟨M,M1⟩, where M1 is a TM that rejects all inputs.
2. If R accepts, accept; if R rejects, reject.”

判断M和拒绝所有输入的图灵机M1是否识别同一种语言(空),如果是,则空返回接受,不是,则非空返回拒绝,这就是ETM的判定机,矛盾!

Computation History 利用计算历史的归约

LBA(线性有界自动机)是一种限制类型的图灵机,不允许带头移出包含输入的带部分。

ALBA可判定

ALBA={⟨M,w⟩| M is an LBA that accepts string w }.判断某LBA是否接受w。

LBA的内存是有限的,这既是它的缺点,也是它的优点:
对于某一有限长的输入,它的可能的计算历史是有限多的:

M是有q个状态和g个符号的LBA,对于长度为n的输入(带子长度),M的格局数为qng^n,所以只要模拟qng^n还没停机,说明它肯定进入了重复的格局,那么即进入了循环,所以就可以拒绝。所以ALBA(判断LBA是否接受输入w)是可判定的

ELBA是不可判定的

ELBA={⟨M⟩|M is an LBA where L(M)=∅}.判断LBA是否不接受任何串。

思路:还是那个套路,证明若ELBA可判定那么ATM也可判定

S = “On input <M,w>, where M is a TM and w is a string:
1. Construct LBA B and the language that B recognizes comprises all accepting computation histories for M on w.
2. Run R on input <B>.
3. If R rejects, accept; if R accepts, reject.”

B包含了M对w的接受格局,如果M接受w,B就非空,R就会返回拒绝,S就接受;如果M不接受w,B就是空的,那么R就接受,S就拒绝,这就是ATM判定机。

ALLCFG是不可判定的

ALLCFG={⟨G⟩| G is a CFG and L(G)=Σ∗}.上下文无关文法的等价性问题。

思路:还是那个套路,证明若ALLCFG可判定那么ATM也可判定

G is designed to generate all strings that are not accepting computation histories for M on w.
Instead of constructing G, we construct a PDA D.
In this instance, D will start by nondeterministically branching to guess which of the succeeding three conditions to check:
1. that do not start with C1,
2. that do not end with an accepting configuration, or
3. in which some Cdoes not properly yield Ci+1 under the reles of M.

5.2 A simple Undecidable Problem 一个简单的不可判定问题

PCP(波斯特对应问题,Post correspondence problem):给出一堆骨牌的集合,骨牌上下都是字符串,问是否存在一种骨牌的序列(骨牌可重复使用,或者不用)使得上下字符串相等。

PCP是不可判定的

证明思路:

从任意的TM M和输入w都能构造一个实例P,使得匹配都是M在w上的接受计算历史。

这样如果能确定这个实例是否有一个匹配,就能确定M是否接受w。

这样需要构造P使得匹配都是M在w上的接受计算历史,在P中选择骨牌,使得每形成一个匹配,便模拟一次M,且在匹配中,每个骨牌都将一个格局的一个或多个位置与下一个格局中的相应位置连接起来。

  1. 为了方便P的构造,假设M在w上从不试图将它的读写头移出纸带的左端点,这要求首先改变M以防止这样的行为。
  2. 修改PCP,要求匹配都从第一个骨牌开始,称这个问题为MPCP。

好长好长的证明,不好概括说明,具体看书把!如果非得概括一下:

骨牌是可以重复的,也可以不用某些骨牌,这是不可判定的原因。

5.3 Mapping Reducibility 映射可归约性

简单的说,“用映射可归约性将问题A转换为问题B“指的是,存在一个可计算函数,它能将问题A的实例转换成问题B的实例。有这个转换函数(归约),就能用B的解决方案来解决A。

定理:如果问题A映射可归约到问题B,B是可判定的,则A也是可判定的。

定理:如果问题A映射可归约到问题B,B是图灵可识别的,则A也是图灵可识别的。

发表评论

电子邮件地址不会被公开。 必填项已用*标注