我的理解是，由于它不可计算，因此当答案为“是”或“否”时，它可能不会停止。这就是为什么它不能被共同递归枚举的原因，因为它不能保证它总是在“否”时停止。
问问题
166 次
1 回答
0
一个问题可能是不可计算的，但仍然是可共同递归枚举的。
可计算集、可判定集或递归集具有 TM，它们总是可以通过接受或拒绝任何输入来停止。
不可计算的集合仍然可以是半可判定的、递归可枚举的或协递归可枚举的，如果它们具有可以通过接受集合中的所有内容（而当输入不在集合中时可能根本无法停止）或通过拒绝所有内容来停止的 TM不在集合中（当输入在集合中时可能根本无法停止）。
显然，如果一个集合既是递归可枚举的又是协递归可枚举的，那么它是递归的（可计算的、可判定的），因为您可以运行两个 TM——一个最终通过接受而停止，另一个最终通过拒绝而停止——而你知道两者之一最终会给你正确的答案。
于 2018-11-30T19:34:40.973 回答