将语言分类为图灵可识别或协同图灵可识别
Classify a language as Turing-recognizable or co-Turing-recognizable
我有这门语言
L = {<M> | M is a TM that accepts w whenever it accepts w^R}
我能够证明这种语言是不可判定的。
但是这种语言是图灵可识别的还是协同图灵可识别的？
如果 TM 可以停止接受语言中的所有字符串，则该语言是 RE。如果 TM 可以停止拒绝所有不属于该语言的字符串，则该语言就是核心语言。要使 L 成为 RE，我们需要知道 TM 在接受 w 时总是接受 w^R。要使 L 成为 coRE，我们需要知道 TM 接受一些 w 但不接受相应的 w^R。既不是RE也不是CORE。
它不是 RE，因为如果某个特定的 TM 恰好接受空语言，因此属于 L，则无法识别这一事实。我们语言的识别器将使我们能够识别接受空语言的 TM，这是不可能的。
它不是 coRE，因为如果某个特定的 TM 恰好接受由单个非回文字符串组成的语言，因此不属于 L，则没有办法去承认这个事实。我们语言的识别器将使我们能够识别接受单个非回文字符串的 TM，这是不可能的。
我有这门语言
L = {<M> | M is a TM that accepts w whenever it accepts w^R}
我能够证明这种语言是不可判定的。
但是这种语言是图灵可识别的还是协同图灵可识别的？
如果 TM 可以停止接受语言中的所有字符串，则该语言是 RE。如果 TM 可以停止拒绝所有不属于该语言的字符串，则该语言就是核心语言。要使 L 成为 RE，我们需要知道 TM 在接受 w 时总是接受 w^R。要使 L 成为 coRE，我们需要知道 TM 接受一些 w 但不接受相应的 w^R。既不是RE也不是CORE。
它不是 RE，因为如果某个特定的 TM 恰好接受空语言，因此属于
L，则无法识别这一事实。我们语言的识别器将使我们能够识别接受空语言的 TM，这是不可能的。它不是 coRE，因为如果某个特定的 TM 恰好接受由单个非回文字符串组成的语言，因此不属于
L，则没有办法去承认这个事实。我们语言的识别器将使我们能够识别接受单个非回文字符串的 TM，这是不可能的。