验证“若L∉RE且L'∉RE则L∪L'∉RE”正确性及相关疑问

嗨，我来帮你理清楚这些关于递归可枚举语言（RE）的问题，咱们一步步来：

这个命题不成立，我们可以构造一个简单的反例来证明：

• 首先，我们知道存在语言 ( A ) 既不属于RE，也不属于co-RE（这类语言可以通过对角线方法构造出来，比如Post问题的解就属于这类）。
• 令 ( L = A )，( L' = \overline{A} )（( A ) 的补集）。
  • 因为 ( A \notin \text{RE} )，所以 ( L \notin \text{RE} )；同时，由于 ( A \notin \text{co-RE} )，意味着 ( \overline{A} \notin \text{RE} )，所以 ( L' \notin \text{RE} )。
  • 但 ( L \cup L' = \Sigma^* )（所有可能的字符串），而 ( \Sigma^* ) 是递归语言（显然属于RE，甚至是递归的）。

这就直接推翻了原命题：两个都不属于RE的语言，它们的并集可以属于RE。

不能，你的理解在这里出现了偏差。咱们先明确几个核心定义：

• RE语言：存在图灵机 ( M )，使得当输入 ( x \in L ) 时，( M ) 停机并接受；当 ( x \notin L ) 时，( M ) 可能停机拒绝，也可能无限循环。
• co-RE语言：存在图灵机 ( M )，使得当输入 ( x \notin L ) 时，( M ) 停机并拒绝；当 ( x \in L ) 时，( M ) 可能停机接受，也可能无限循环。等价于 ( \overline{L} \in \text{RE} )。

你把 ( L \notin \text{RE} ) 理解成“对所有不在L中的输入x，图灵机会拒绝，否则不拒绝”——但这其实是co-RE的定义，不是 ( L \notin \text{RE} ) 的定义。( L \notin \text{RE} ) 仅仅表示不存在能接受L的图灵机，但这完全不意味着L的补集是RE。比如刚才提到的语言 ( A )，它既不在RE里，也不在co-RE里，因为它的补集也不在RE里。

当然不能，还是用刚才的例子来验证：

• 取 ( L = A )（那个既不在RE也不在co-RE的语言），那么 ( L \notin \text{RE} )，而 ( L^c = \overline{A} ) 同样不在RE里（因为 ( A \notin \text{co-RE} )，就等价于 ( \overline{A} \notin \text{RE} )）。

只有当L是递归语言时，L和它的补集才同时属于RE（也属于co-RE），但对于非递归的语言，存在大量既不在RE也不在co-RE的情况，所以这个推论不成立。

内容的提问来源于stack exchange，提问作者Ilan Aizelman WS