为什么不递归可枚举语言不可判定

Question

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

在可计算性理论，一个不可判定问题由针对特定是/不需要回答情况的家庭 的，例如 ，在给定任何问题实例为 输入的情况下，没有计算机程序，终止并在有限的 步数之后输出所需的答案。更正式地说，一个不可判定的问题是一个问题 其语言不是递归集

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

Answer 1

递归可枚举的语言/集合也被称为半可判定的。它们不是可判定的，因为没有一台机器会查看输入并且说“是”或“否”（正确）。半决定意味着你可以编写一个机器来查看输入，并且如果输入是在集合中则为是，或者如果输入不在集合中则停止。 半可判定原来是相当于递归可枚举以同样的方式，可判定相当于递归： -

如果你有一个枚举递归可枚举语言图灵机R，你可以制作一台新的机器D，它接受可能或不可能在语言/设置中的输入。 D运行R直到R输出该集合的第一个元素，然后D将其与其输入进行比较。如果它们匹配，则返回“是”结果。如果它们不匹配，它会继续运行R直到它获得下一个元素，依此类推。由于R从不停止（因为语言只能递归枚举，而不是递归），所以D会回答是或不停止。相反，如果您有一台图灵机D可以回答是或不能停机，那么您可以制作一台新机器R，它使用通常的技术通过不同的输入一次一步地运行多个D实例：所有可能或可能不在集合中的元素。每次D的并行执行中止并回答“是”时，R输出D的输入，并在所有其余输入上继续执行D. R永远不会停止（因为有一些D不会停止的输入），但最终它会输出D回答“是”的每个元素，即集合/语言中的每个元素。

不要因为认为存在三种（不相交）的集合而感到困惑：可判定的，半可判定的和不可判定的。有两种：可判定和不可判定。所有可判定的集合也是半可判定的（尽管这样说非常不寻常）。一些不可判定的集合也是半可判定的。这与说所有可枚举集合都是递归可枚举，以及一​​些不可枚举集合是递归可枚举相同。

Answer 2

甲semidecidable问题（或等价一个递归可枚举的问题）可以是：

1. 可判定：如果问题及其补均为semidecidable（或递归可枚举的），则该问题是可判定的（递归）。

2. 不可确定：如果问题是semidecidable和它的补码是semidecidable（即，不是递归可枚举）。

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

什么维基词条中说的是：

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

一般来说，半判定问题（递归可枚举）可以是可判定的（递归的）或不可判定的（非递归可枚举的）。

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

Answer 3

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

总结：

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