证明集合 {⟨M⟩|L(M) = (L(M))R,即若w ∈ L(M)有wR ∈ L(M)} 是不可判定的,进一步证明是非递归可枚举的。
时间: 2024-04-23 10:24:01 浏览: 49
为了证明集合 {⟨M⟩|L(M) = (L(M))R} 是不可判定的,我们可以采用对角化的思想。
假设存在一个图灵机 R,可以判定一个图灵机 M 的语言是否满足 L(M) = (L(M))R。现在我们构造一个新的图灵机 S:
S = "对于任意输入 x,进行如下操作:
1. 将 x 反转得到 xR
2. 运行 R 判断 M 是否接受字符串 xR
3. 如果 R 认为 M 接受 xR,拒绝;否则接受"
现在考虑 S 是否满足 L(S) = (L(S))R。如果 L(S) = (L(S))R,那么 S 应该被 R 判定为不接受任何输入,因为如果 S 接受了某个输入 x,那么 S 也应该接受 xR,因为 xR 是 x 的逆序,L(S) 是对所有字符串取逆序后的语言。但是这与 S 的定义矛盾,因为 S 接受所有不满足 L(M) = (L(M))R 的图灵机 M 的描述。
因此,我们得出结论,不存在一个图灵机可以判定集合 {⟨M⟩|L(M) = (L(M))R} 是否成立,即该集合是不可判定的。
接下来,我们需要证明该集合是非递归可枚举的。我们可以构造一个递归可枚举集合 A,使得 A 形如 {⟨M, w⟩| M 是一个图灵机,且 w ∈ L(M)}。然后,我们可以构造一个图灵机 T:
T = "对于任意输入 x,进行如下操作:
1. 将 x 拆分为 ⟨M, w⟩ 的形式
2. 构造一个新的图灵机 M',使得 L(M') = L(M) ∪ {wR}
3. 运行 R 判断 M' 是否满足 L(M') = (L(M'))R
4. 如果 R 认为 M' 满足条件,接受;否则继续"
显然,T 能够枚举所有满足 L(M) = (L(M))R 的图灵机 M 和对应的字符串 w。如果 {⟨M⟩|L(M) = (L(M))R} 是递归可枚举的,那么 T 也可以判定该集合,进而判定 A,但是 A 是已知的非递归可枚举集合,因此 {⟨M⟩|L(M) = (L(M))R} 也必须是非递归可枚举的。
综上所述,集合 {⟨M⟩|L(M) = (L(M))R} 是不可判定的,且是非递归可枚举的。