我有这种语言
L = {<M> | M is a TM that accepts w whenever it accepts w^R}
我能够证明这种语言是不可判定的。
但是这种语言是图灵可识别的还是可识别的共图灵？
如果 TM 可以停止接受该语言中的所有字符串，则该语言为 RE。如果 TM 可以停止拒绝该语言中不是该语言的所有字符串，则该语言就是 coRE。为了使L成为 RE，我们需要能够分辨出 TM 在接受w时总是接受w^R。为了使L成为coRE，我们需要能够分辨TM接受一些w但不接受相应的w^R。它既不是RE，也不是coRE。
-
它不是RE，因为如果一个特定的TM碰巧接受空语言，因此属于
L，就没有办法识别这个事实。我们语言的识别器将允许我们识别接受空语言的 TM，这是不可能的。 -
它不是coRE，因为如果一个特定的TM碰巧接受由单个非回文字符串组成的语言，因此不属于
L，则无法识别这一事实。我们语言的识别器将允许我们识别接受单个非回文字符串的 TM，这是不可能的。