TOC中的不可判定性与可还原性

可判定问题 如果我们能构造一个图灵机，它会在有限的时间内停止每个输入，并给出“是”或“否”的答案，那么问题是可以解决的。一个可判定问题有一个算法来确定给定输入的答案。

例子

• 两种常规语言的等价性： 给定两种正则语言，有一个算法和图灵机来决定两种正则语言是否相等。
• 正规语言的有限性： 给定一种正则语言，有一个算法和图灵机来决定正则语言是否有限。
• 语境无关语言的空洞性： 给定一种上下文无关的语言，无论CFL是否为空，都有一个算法。

不可判定的问题 如果没有图灵机总是在有限的时间内停下来回答“是”或“否”，那么问题是不可判定的。不可判定问题没有算法来确定给定输入的答案。

例子

• 上下文无关语言的歧义： 给定一种与上下文无关的语言，不存在图灵机器，它总是在有限的时间内停止，并给出语言是否模糊的答案。
• 两种上下文无关语言的等价性： 给定两种上下文无关语言，没有一种图灵机器总是在有限的时间内停止，并给出两种上下文无关语言是否相等的答案。
• CFG的所有内容或完整性： 给定一个CFG和输入字母表，CFG是否会生成所有可能的输入字母表字符串(∑*)这是无法确定的。
• CFL、CSL、REC和REC的规律性： 给定一个CFL、CSL、REC或REC，确定这种语言是否为正则语言是不可判定的。

注：两个常见的不可判定问题是TM的停止问题和PCP（通信后问题）。半可判定问题 对于“是”和“否”，图灵回答“是”，对于“不可判定的”问题的子集，图灵回答“不可判定的”。 半可判定和可判定问题之间的关系如图1所示：

赖斯定理 递归可枚举语言上的每个非平凡（答案未知）问题都是不可判定的。例如。；如果一种语言是递归可枚举的，那么它的补码是否是递归可枚举的是不可判定的。

可约性与不可判定性 语言A可以简化为语言B（表示为A）≤B） 如果存在一个函数f，它将a中的字符串转换为B中的字符串，如下所示：

w ɛ A <=> f(w) ɛ B

定理1：如果≤B是可判定的，那么A也是可判定的。 定理2：如果≤A是不可判定的，那么B也是不可判定的。

问题：以下哪项是不可判定的？

1. G是CFG。L（G）=ɸ吗？
2. G是CFG。是L（G）=∑*?
3. M是一台图灵机。L（M）正常吗？
4. A是DFA，N是NFA。L（A）=L（N）吗？

A.3只 B.仅限3号和4号 C.仅限1、2和3 D.仅限2和3

说明：

• 选项1是CFG是否为空，这个问题是可以判定的。
• 选项2是CFG是否会生成所有可能的字符串（CFG的所有内容或完整性），这个问题是无法确定的。
• 选项3是TM生成的语言是否为正则语言是不可判定的。
• 选项4是DFA和NFA生成的语言是否相同是可判定的。所以选项D是正确的。

问题：以下哪些问题是可判定的？

1. 给定的程序是否产生过输出？
2. 如果L是上下文无关的语言，那么L’也是上下文无关的吗？
3. 如果我是正规语言，那么我也是正规语言？
4. 如果L是递归语言，那么L’也是递归的？

A.1,2,3,4 B.1,2 C.2,3,4 D.3,4

说明：

• 由于正则语言和递归语言在互补下是封闭的，选项3和4是可判定的问题。
• 上下文无关的语言在补语下不是封闭的，选项2是不可判定的。
• 选项1也是不可判定的，因为没有TM来确定给定程序是否会产生输出。 因此，选项D是正确的。

问题：考虑三个决策问题P1、P2和P3。众所周知，P1是可判定的，P2是不可判定的。以下哪一项是正确的？

A.如果P2可还原为P3，则P3是不可判定的 B.如果P3可还原为P2的补码，则P3是可判定的 C.如果P3可还原为P2，则P3是不可判定的 D.如果P1可还原为P3，则P3是可判定的 说明：

• 选项A表示P2≤P3。根据所讨论的定理2，如果P2是不可判定的，那么P3是不可判定的。假设P2是不可判定的，那么P3也是不可判定的。所以选择 （A） 这是正确的 .
• 选项C表示P3≤P2。根据所讨论的定理2，如果P3是不可判定的，那么P2是不可判定的。但对于P3的不可判定性并没有给出质疑。所以选择 （C） 这是不对的。
• 选项D显示P1≤P3。根据所讨论的定理1，如果P3是可判定的，那么P1也是可判定的。但对于P3的可判定性并没有给出质疑。所以选择 （D） 这是不对的 .
• 选项（B）表示P3≤P2’。根据所讨论的定理2，如果P3是不可判定的，那么P2’是不可判定的。但对于P3的不可判定性并没有给出质疑。所以选择 （B） 这是不对的 .

测验 论不可判定性

本文由 奏鸣曲 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论