computer-science - 为什么递归可枚举语言不是不可判定的

Question

这是维基百科中可判定的定义

在可计算性理论中，一个不可判定的问题由一系列需要特定是/否答案的实例组成，因此没有计算机程序可以在给定任何问题实例作为输入的情况下终止并在有限数量后输出所需的答案的步骤。更正式地说，不可判定问题是语言不是递归集的问题

递归集是递归可枚举集的子集。有一些递归可枚举的语言在递归集合之外。那么为什么递归可枚举语言不是不可判定的呢？

Answer 1

递归可枚举语言/集合也称为半可确定的。它们是不可判定的，因为没有一台机器可以查看输入并（正确地）说是或否。半可判定意味着您可以编写一台机器，它查看输入并在输入在集合中时说“是”，或者如果输入不在集合中则无法停止。Semi-decidable结果证明等效于递归可枚举，就像可确定等效于递归一样：-

如果您有一个枚举递归可枚举语言的图灵机 R，您可以制作一个新机器 D，它接受可能是或可能不在语言/集合中的输入。D 运行 R 直到 R 输出集合的第一个元素，然后 D 将其与其输入进行比较。如果它们匹配，则返回“是”结果。如果它们不匹配，它会继续运行 R，直到它获得下一个元素，依此类推。由于 R 永远不会停止（因为该语言只能递归枚举，而不是递归），D 将回答是或不停止。

相反，如果您有一台回答是或未能停止的图灵机 D，您可以制造一台新机器 R，它使用通常的技术一次并行运行 D 的多个实例，并使用各种输入：所有元素可能在也可能不在集合中。每次 D 的并行执行之一以“是”的答案停止时，R 输出 D 的输入，并继续在所有剩余的输入上执行 D。R 永远不会停止（因为有些输入 D 不会停止），但最终它将输出 D 回答“是”的每个元素，即集合/语言中的每个元素。

不要误以为存在三种（不相交的）集合：可判定的、半可判定的和不可判定的。有两种：可判定的和不可判定的。所有可判定的集合也是半可判定的（尽管这样说是不寻常的）。一些不可判定的集合也是半可判定的。这就像说所有可枚举集都是递归可枚举的，而某些不可枚举集是递归可枚举的。

Answer 2

一个半可判定问题（或等效的递归可枚举问题）可能是：

1. 可判定的：如果问题及其补码都是半可判定的（或递归可枚举的），那么问题是可判定的（递归的）。

2. Undecidable：如果问题是半可判定的并且它的补码不是半可判定的（也就是说，不是递归可枚举的）。

重要提示：请记住，可判定（递归）问题也是半可判定（递归可枚举）的。相反，如果一个问题不是递归可枚举的（semidecidable），那么它就不是递归的（decidable）。

维基百科条目说的是：

不可判定的部分可判定问题称为不可判定问题。

通常，半可判定问题（递归可枚举）可以是可判定（递归）或不可判定（非递归可枚举）。

另请注意，一个问题及其补充可能都（或只是其中之一）甚至不是半可判定的（非递归可枚举的）。还要注意，如果一个问题是递归的，它的补码也是递归的。

Answer 3

我相信问题集的图形表示在这里可能会更有帮助（不同集的大小在这里没有意义）。

总结一下：

1. 每个可判定（递归）问题也是半可判定（递归可枚举）的。
2. 每个不可判定（递归）的半可判定（递归可枚举）问题都是不可判定的。
3. 有不可判定的问题不是半可判定的（递归可枚举）。