Reducibility，Use B solver to solve A
旨在将一个问题转化为另一个问题，使得可以用第二个问题的解来解第一个问题。
不可判定问题
一般将 归约到相应的问题, 就可利用 的不可判定性证明问题的不可判定性。
当 不方便使用的时候，以下定理也可以用来证明不可判定性。
= { <M,w> | M 是一个图灵机，且对输入w停机 ｝
确定一个图灵机对给定的输入是否停机的问题被称为停机问题 (halting problem)。
假设图灵机 判定 ，由之可以构造图灵机 来判定
S =“在输入<M,w>上，此处<M,w>是图灵机M和串w的编码：
- 在输入<M,w>上运行图灵机R。
- 如果 R 拒绝， 则拒绝。
- 如果 R 接受， 则在 w 上模拟 M, 直到它停机。
- 如果 M 已经接受， 则接受；如果 M 巳经拒绝， 则拒绝。”
显然， 如果R判定 ，则S判定 。
因为 是不可判定的，故是 不可判定的。
Let’s assume that TM decides and construct TM to decide .
S = “On input <M,w>, an encoding of a TM and a string :
- Run TM on input <M,w>.
- If rejects, reject .
- If accepts, simulate on until it halts.
- If has accepted, accept ; if M has rejected, reject .”
Clearly, if decides , then decides .
Because is undecidable, also must be undecidable.
= { <M> | M 是一个图灵机，且 L(M)＝ }
💡 设 R 是判定 的一个图灵机，怎样用 R 来构造判定 的图灵机 S ？
当 S 收到输入 ⟨M, w⟩ 时，S 应该怎样运行？
使得除了 w 之外， M 对所有串都拒绝；但输入 w， 它如常运行。
再用 R 来测定这个是否识别空语言
如果 R 接受 S，则说明 M 不接受 w，即 M 是空集
- = “On input :
- If , reject .
- If , run on input and accept if does.”
Assume that TM decides and construct TM that decides as follows.
- = “On input ⟨M, w⟩, an encoding of a TM and a string :
- Use the description of M and w to construct the TM .
- Run on input ⟨M, w⟩.
- If accepts, reject ; if R rejects, accept .”
If were a decider for , would be a decider for . However, is undecideable, so must be undecidable.
- = { <M,w> | M 是一个图灵机，L(M) 是一个正则语言 ｝
- = { <M1, M2> | M1 和 M2 都是一个图灵机，且L(M1)＝L(M2) }
- = { <G> | G是一个CFG，且 L(G) = }
波斯特对应问题
Post Correspondence Probelm
- A collection of dominos looks like
- 任务是将这些进行排列（允许重复），使得在阅读顶部符号后得到的串与阅读底部符号后得到的串相同。这样的排列称为一个匹配 (match)。
- 例如，其中一种匹配情况：
- For some collections of dominos, finding a match may not be possible.
PCP= { <P> | ，且P有匹配｝是不可判定的。
利用计算历史的归约
Reductions Via Computation Histories：证明 可归约到某些语言的重要技术
- 设M是一个图灵机，w 是一个输入串。
- M 在 w 上的一个接受计算历史 (accepting computation history) 是一个格局序列，其中 是M 在w上的起始格局， 是 M 的一个接受格局， 且每个 都符合M 的规则。
- M 在w上的一个拒绝计算历史 (rejecting computation history) 可类似定义，只是 应是一个拒绝格局。
线性界限自动机 (linear bounded automaton, LBA)
一种储存受到限制的图灵机。它不允许其读写头离开包含输入的带子区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就保持在原地不动。
- = { <M,w> | M 是一个接受串 w 的 LBA } 是可判定的
- = { <M> | M 是一个 LBA，且L(LBA)＝ } 是不可判定的
映射可归约性
Mapping reducibility
存在一个可计算函数 (computable function)，它将问题 A 的实例转换成问题 B 的实例，就能用 B 的解决方案来解 A。
定义：语言 A 是映射可归约到语言 B 的，如果存在可计算函数 使得每个 w,
（记做 ）。称函数 为从 A 到 B 的归约。
定理
- 如果 且 是可判定的， 则 也是可判定的。
- 如果 且 不是可判定的， 则 也不是可判定的。
- 如果 且 （不）是图灵可识别的， 则 也（不）是可图灵可识别的。
How to apply above theorems?
- To prove 𝐵 is undecidable:
Show undecidable 𝐴 is reducible to 𝐵. (often 𝐴 is )
Assume TM 𝑅 decides 𝐵 and construct TM 𝑆 deciding 𝐴.
Contradiction.
- To prove 𝐵 is T-unrecognizable
Show T-unrecognizable 𝐴 is mapping reducible to 𝐵, then give reduction function 𝑓.
例题
既不是图灵可识别的，也不是补图灵可识别的。
- 证明 可归约到 。
- Construct the following two machines M1 and M2. M1 = “On any input: 1. Reject.” M2 = “On any input: 1. Run on . 2. Accept if accept.”
- Output <M1,M2>.”
归约函数如下：
F = “On input <M,w>, where M is a TM and a string:
- 证明 可归约到
- Construct the following two machines M1 and M2.
- Output <M1,M2>.”
归约函数入下：
G = “On input <M,w>, where M is a TM and a string:
M1 = “On any input: 1. Accept.”
M2 = “On any input: 1. Run on . 2. Accept if accept.”
莱斯定理
Rice's theorem
Suppose that C is a proper, none-emptysubset of the class of all recursively enumerable languages. Then the following problem is undecidable: Given a Turing machine , is ?
- Let P be any nontrivial property of the language of a Turing machine. Prove that the problern of determining whether a given Turing machine's language has property P is undecidable.
- In more formal terins, let P be a language consisting of Turing machine descriptions where P fulfills two conditions.
- First, P is nontrivial —— it contains some, but not all, TM descriptions.
- Second, P is a property of the TMs language —— whenever , we have iff . Here, and are any TMs, prove that P is an undecidable language.
对于任何非平凡的性质（非全为真或全为假）的递归可枚举语言集合，判定一个任意图灵机是否接受该集合中的语言是不可判定的。
非平凡的性质指的是至少有一个图灵机的语言具有该性质，且至少不具有该性质。
假设我们有一组图灵机，每个图灵机都接受一种语言。现在，我们想要判断这些图灵机是否具有某个特定的性质。这个性质可以是各种各样的，比如：
- 该图灵机接受的语言是否包含偶数个字符串。
- 该图灵机接受的语言是否至少包含一个回文字符串。
根据莱斯定理，只要这个性质是非平凡的（即不是所有图灵机都满足或都不满足），那么就不存在一个算法能够对于所有的图灵机判断其是否具有这个性质。
Exam-2022-2(b) Prove Rice’s Theorem (you can use the recursion theorem).
Give the following assumption:
- The problem “Given a Turing machine , is ? ” can be decided by the TM .
- P is a non-trivial property, and the problem “Is a Turing Machine can decide ?” can be decided by the TM .
- is a Turing Machine that does not have the property .
: “判断一个图灵机是否能接受一个字符串” ，即它是一种
= “On input :
- Use and to construct the following TM
- Stimulate on . Reject if it halts and reject. Proceed to stage 2 if it accepts.
- Stimulate on input . Accept if it accepts.
= “On input x:
- Use TM to determine whether . Accept if Yes, otherwise reject. ”
Based on the above construction, we can reduce the S to . Since is undecidable, it follows that is also undecidable.
递归语言
A language is Turing-enumerable if and only if it therc is a Turing machine that enumerates (all string in) it.
Theorem: A language is recursively enumerable if and only if it is Turing-enumerable.
Theorem: A language is recursive if and only if both it and its complement are recursively enumerable.