证明一种语言在 RE/R/coRE
Proving a language is in RE/R/coRE
假设我们有一个像这样的图灵机函数：
() = { 1, for any where () halts only if w is a palindrome of even length
0, otherwise
如何证明它属于（或不属于）RE, R, coRE
我的意思是，我知道我们可以使用 f-halt 进行图灵归约来证明它不属于 R。但是 RE/coRE 呢？
如果我们可以暂停接受语言中的任何字符串，那么该语言就是 RE。如果我们可以停止拒绝任何不属于该语言的字符串，那么该语言就是核心语言。 R是RE和coRE的交集；一种语言是 R，如果我们可以暂停接受该语言的字符串，暂停拒绝非该语言的字符串。
您已经知道该语言不是 R。这也可以通过莱斯定理看出：仅在偶数长度的回文上停止是公认语言（EPAL 的子集）的语义属性，所以包含问题是不可判定的。这告诉您该语言不能同时是 RE 和 coRE，尽管它可能两者都不是。
给定一台机器M，我们能否确定它只接受长度为偶数的回文字符串？这似乎不太可能。我们需要一种方法来确保所有字符串——可能是无限多的——都是偶数长度的回文。不能随便找个反例就完事了
给定一台机器M，我们能否确定它不仅接受偶数回文字符串？我们一定可以！我们可以交错执行这台机器的副本，这样任意多个可能的输入字符串都可以获得任意多的计算时间；如果 M 接受任何特定的字符串，我们最终可以找到，如果它接受一个不是偶数长度的回文，我们最终可以知道。
所以，这种语言：
- 是核心
- 不是 RE
- 不是R
假设我们有一个像这样的图灵机函数：
() = { 1, for any where () halts only if w is a palindrome of even length
0, otherwise
如何证明它属于（或不属于）RE, R, coRE
我的意思是，我知道我们可以使用 f-halt 进行图灵归约来证明它不属于 R。但是 RE/coRE 呢？
如果我们可以暂停接受语言中的任何字符串，那么该语言就是 RE。如果我们可以停止拒绝任何不属于该语言的字符串，那么该语言就是核心语言。 R是RE和coRE的交集；一种语言是 R，如果我们可以暂停接受该语言的字符串，暂停拒绝非该语言的字符串。
您已经知道该语言不是 R。这也可以通过莱斯定理看出：仅在偶数长度的回文上停止是公认语言（EPAL 的子集）的语义属性，所以包含问题是不可判定的。这告诉您该语言不能同时是 RE 和 coRE，尽管它可能两者都不是。
给定一台机器M，我们能否确定它只接受长度为偶数的回文字符串？这似乎不太可能。我们需要一种方法来确保所有字符串——可能是无限多的——都是偶数长度的回文。不能随便找个反例就完事了
给定一台机器M，我们能否确定它不仅接受偶数回文字符串？我们一定可以！我们可以交错执行这台机器的副本，这样任意多个可能的输入字符串都可以获得任意多的计算时间；如果 M 接受任何特定的字符串，我们最终可以找到，如果它接受一个不是偶数长度的回文，我们最终可以知道。
所以，这种语言：
- 是核心
- 不是 RE
- 不是R