为什么递归枚举语言不能确定

Question

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

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

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

Answer 1

递归可枚举语言/集也称为半可判定语言。它们是不可分辨的，因为没有一台机器可以查看输入，并(正确地)说“是”或“否”。半可判定意味着您可以编写一台机器，它可以查看输入，如果输入在集合中，可以说“是”，如果输入不在集合中，则不能停止。半可判定的结果是等价于递归可枚举的，就像可判定等价于递归：

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

相反，如果你有一个图灵机D，它回答是或不能停止，你可以制造一个新机器R，它使用通常的技术，一步一步地运行几个D的实例，每次都有不同的输入:所有的元素可能在集合中，也可能不在集合中。每次D的并行执行之一以“是”的回答停止时，R输出D的输入，并继续对所有剩余的输入执行D。R永远不会停止(因为有些输入D不会停止)，但它最终会输出D回答为“是”的每个元素，即集合/语言中的每个元素。

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

Answer 2

一个半可分解的问题(或等效的递归可枚举问题)可以是：

1. Decidable：如果问题及其补语都是半可计数的(或递归可枚举的)，则如果问题是半可重的，并且它的补不可半可列(即不是递归枚举的)，则问题是可判定的(recursive).
2. Undecidable：。

重要注意事项：记住，可判定的(递归)问题也是半可选的(递归可枚举的)。相反，如果一个问题不是递归枚举的(半可计数的)，那么它就不是递归的(可判定的)。

维基百科的条目是这样写的：

部分可判定问题(非DECIDABLE )称为不可判定问题。

通常，半可分解问题(递归枚举)可以是可判定的(递归的)，也可以是不可判定的(非递归枚举的)。

还注意到，一个问题和它的补语都可能(或者只是其中的一个)甚至不是半可判定的(非递归计数)。还请注意，如果一个问题是递归的，那么它的补语也是递归的。

Answer 3

我认为用图形表示问题集在这里可能会更有帮助(不同集合的大小在这里没有意义)。

概括地说：

每个可判定的(递归的)问题也是半可判定的(递归的enumerable).

• Every半可判定的(递归的可计数的)问题是不可判定的(递归的) undecidable.

• There是不可判定的不可判定的问题(递归可计数的)。

​

​