第五章：可规约性

5 Reducibility

关于其他章节的内容，请点这：《计算理论导引》学习笔记

5.1 Undecidable Problems from Language Theory

可归约性

如果问题A可归约为问题B，那么只要解决了问题B，就可以解决问题A了，即\( A \longleftarrow B\)
所以
如果B是可判定的，那么A也是可判定的
如果A是不可判定的，那么B也是不可判定的

下面以\( A_{TM}\)不可判定为基础，证明某些语言不可判定：
假设另一语言可判定，令其decider为R \( \longrightarrow\) 用R构造出\( A_{TM}\)的decider S \( \longrightarrow\) \( A_{TM}\)可判定
矛盾出现，假设不成立，证毕。
接下来是一大波例子（from Language Theory）:

停机问题

\(HALT_{TM} = \{\langle M,w \rangle | \text{ M is a TM and M halts on input w }\} \).

S = “On input <M,w>, an encoding of a TM M and a string w:
1. Run TM R on input <M,w>.
2. If R rejects, reject.
3. if R accepts, simulate M on w until it halts.
4. If M has accepted, accept; if M has reject, reject.”

\( E_{TM}\)不可判定

\( E_{TM} = \{\langle M \rangle | \text{ M is a TM and L(M) = } \emptyset\}\).

The only string the machine can now accept is w, so its language will be nonempty iff it accepts w.
\( M_1\) = “On input x:
1. If \( x \ne 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 \( M_1\) just described.
2. Run R on input \( \langle M_1 \rangle\).
3. If R accepts, reject; if R rejects, accept.”

\( REGULAR_{TM}\)不可判定

\( REGULAR_{TM} = \{\langle M \rangle | \text{ 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. Construct the following TM \( M_2\).
\( M_2\) = “On input x:

  1. If x has the form \( 0^n1^n\), accept.

  2. If x does not have this form, run M on input w and accept If M accepts w.”

2. Run R on input \( \langle M_2 \rangle\).
3. If R accepts, accept; if R rejects, reject.”

Similarly, the problems of testing whether the language of a Turing machine is a context-free language, a decidable language, or even a finite language can be shown to be undecidable with similar proofs.
In fact, a general result, called Rice’s theorem, states that determining any property of the languages recognized by Turing machines is undecidable.
We give Rice’s theorem in Problem 5.28.

\( EQ_{TM}\)不可判定

\( EQ_{TM} = \{\langle M_1,M_2 \rangle | M_1\text{ and }M_2\text{ are TMs and } L(M_1) = L(M_2)\}\).

这里以\( E_{TM}\)为证明基础：\( EQ_{TM} \longleftarrow E_{TM}\).

S = “On input <M>, where M is a TM:
1. Run R on input \( \langle M,M_1 \rangle\), where \( M_1\) is a TM that rejects all inputs.
2. If R accepts, accept; if R rejects, reject.”

Computation History

Let M be a Turing machine and w an input string.
An accepting computation history for M on w is a sequence of configurations, \( C_1,C_2,\ldots,C_l\),
where \( C_1\) is the start configuration of M on w, \( C_l\) is an accepting configuration on M,
and each \( C_i\) legally follows from \( C_{i-1}\) according to the rules of M.
A rejecting computation history for M on w is defined similarly, except that \( C_l\) is a rejecting configuration.

Linear Bounded Automaton

A LBA(linear bounded automaton is a restricted type of Turing machine
wherein the tape head isn’t permitted to move off the portion of the tape containing the input.
If the machine tries to move its head off either end of the input, the head stays where it is–in the same way that the head will not move off the left-hand end of an ordinary Turing machine’s tape.

Using a tape alphabet larger than the available memory to be increased up to a constant factor.
Hence we say that for an input of length n,
the amount of memory available is linear in n–thus the name of this model.

LBA的内存是有限的，这既是它的缺点，也是它的优点：
对于某一有限长的输入，它的可能的计算历史是有限多的：
Let M be an LBA with q states and g symbols in the tape alphabet. There are exactly \( qng^n\) distinct configurations of M for a tape of length n.
证明略

再次引出一大波例子

利用Computation History和LBA，又可以证明一大波语言不可判定:

\( A_{LBA}\)不可判定

\( A_{LBA} = \{\langle M,w \rangle | \text{ M is an LBA that accepts string w }\}\).

L = “On input <M,w> where M is an LBA and w is a string:
1. Simulate M on w for \( qng^n\) steps or until it halts.
2. If M has halted, accept if it has accepted and reject if it has rejected. If it has not halted, reject.”

\( E_{LBA}\)不可判定

\( E_{LBA} = \{\langle M \rangle | \text{M is an LBA where } L(M) = \emptyset\}\).

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.”

\( ALL_{CFG}\)不可判定

\( ALL_{CFG} = \{\langle G \rangle | \text{ G is a CFG and } L(G) = \Sigma^*\}\).

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 \( C_1\),
2. that do not end with an accepting configuration, or
3. in which some \( C_i\) does not properly yield \( C_{i+1}\) under the reles of M.

5.2 A simple Undecidable Problem

终于来了个实际点的例子：PCP(Post Correspondence Problem)
\( P = \{ [\frac{t_1}{b_1}],[\frac{t_2}{b_2}],\dots,[\frac{t_k}{b_k}]\}\).
\( PCP = \{\langle P \rangle | \text{ P is an instance of the Post Correspondence Problem with a match }\}\).
首先要学会这种把实际问题转化为语言的思tao想lu
然后仔细看这个问题的定义，你会发现骨牌是可以重复的，这就是这个问题不可判定的根本原因
所以下面这个长达6页的证明非常有技巧性，略去🙂

5.3 Mapping Reducibility

Mapping reducibility(many-one-reducibility) is a simple type of reducibility with formal notion of reducing one problem to another.

Doing so allows us to use reducibility in more refined ways, such as for proving that certain languages are not Turing-recognizalbe and for applications in complexity theory.

Roughly speaking, being able to reduce problem A to problem B by using a mapping reducibility means that a computable function exists that converts instances of problem A to instances of problem B.
If we have such a conversion function, called a reduction, we can solve A with a solver for B. The reason is that any instance of A can be solved by first using the reduction to convert it to an instance of B and then applying the solver for B.

A function \( f: \Sigma^* \longrightarrow \Sigma^*\) is a computable function if some Turing machine M, on every input w, halts with just f(w) on its tape.

Language A is mapping reducible to language B, written \( A \le_m B\),
if there if a computable function \( f: \Sigma^* \longrightarrow \Sigma^*\),
where for every w, \( w \in A \iff f(w) \in B\).
The funtion f is called the reduction from A to B.

和5.1有什么区别呢？我们先来看一下怎么用Mapping Reducibility证明停机问题：
We can demonstrate a mapping reducibility from \( A_{TM}\ to\ HALT_{TM}\) as follows.
To do so, we must present a computable function f that takes input of the form <M,w> and returns output of the form <M’,w’>, where
\( \langle M,w \rangle \in A_{TM} \iff \langle M’,w’ \rangle \in HALT_{TM}\).
The following machine F computes a recuction f.
F = “On input <M,w>:
1. Construct the following machine M’.
M’ = “On input x:

  1. Run M on x.

  2. If M accepts, accept.

  3. If M rejects, enter a loop.”

2. Output <M’,w>.”

其实本质还是一样的，不过形式变了而已
在5.1里，证明的关键是用\( HALT_{TM}\)的decider构造\( A_{TM}\)的decider
在5.3里，证明的关键是把\( A_{TM}\)的输入转化成\( HALT_{TM}\)的输入，使其同时被接受：
\( \langle M,w \rangle \in A_{TM} \iff \langle M’,w’ \rangle \in HALT_{TM}\).

The sensitivity of mapping reducibility to complementation is important in the use of reducibility to prove nonrecognizability

If \( A \le_m B\) and B is Turing-recognizable, then A is Turing-recognizable.
If \( A \le_m B\) and A is not Turing-recognizable, then B is not Turing-recognizable.

例子：
\( EQ_{TM}\) is neither Turing-recognizable nor co-Turing-recognizable.
reduction function:略

Leave a Reply