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

Question

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

In computability theory, an undecidable problem consists of a family of instances for which a particular yes/no answer is required, such that there is no computer program that, given any problem instance as input, terminates and outputs the required answer after a finite number of steps. More formally, an undecidable problem is a problem whose language is not a recursive set

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

Answer 1

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

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

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

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