使用图灵可判定语言的闭包结果

Question

我有一种语言 L1 = {w in {0,1}*| w包含相同数量的1和0}并且我有一个决定L1的TM M。

我想证明 L2 = {w in {0,1}*| w 包含的 1 多于 0} 是图灵可判定的。

我使用了 "closed under complement" 方法并证明了 M' 决定了 L1 (~L1) 的补集。

我的问题是，我能否假设 ~L1 = (L2 或 ~L2) 并得出结论，因为 M' 决定 ~L1，所以 L2 和 ~L2 都是可判定语言？

感谢您的任何建议 （不好意思，这里还没想好如何使用LaTex...）

Answer 1

我只是想充实 Wellbog 的回答。这是 L1（读 n₁(w) 为 "number of 1's in w"）：

L1 = {w∈ {0,1}^*: n₁(w) = n₀(w)}

这里是 L2：

L2 = {w∈ {0,1}^*: n₁(w) > n₀(w)}

从另一边看，L1-bar 是：

L1-bar = {w∈ {0,1}^*: n₁(w) > n₀(w) 或 n ₁(w) < n₀(w)}

很明显，L1-bar 和 L2 是不同的。