theory - 为什么图灵可识别语言的类没有在 Complement 下关闭？

Question

我正在研究图灵机，我已经展示了 Turing-Decidable 是如何为 Union、Intersection、Concatenation、Complement 和 Kleene Star 的操作关闭的。接下来我做了一些演示来展示 T-Recognizable 语言是如何为 Union、Intersection、Concatenation 和 Kleene Star 关闭的。

现在我试图回答一个问题，以说明为什么 T-Recognizable 语言的类对于 Complementation 的操作没有关闭，但我无法理解。有人可以解释一下吗？

谢谢

Answer 1

1. T-recog corresponds to semi-decidable (r.e.).

2. Convince yourself that a language is exaclty then decidable, when both, the language itself and its relative complement are r.e.

3. Convince yourself that there are r.e. languages that are not decidable (e.g. Halteproblem)

4. Assume that the class of r.e. languages is closed under complementation and derive a contradiction to the facts mentioned in 2. and 3.