证明递归语言集在反转下是封闭的？

考虑语言 L，如果存在一个图灵机 (TM)，它会生成一个数字序列 T*，而这些数字序列恰好包含 L 的成员，那么在字母 T 上的字母 T 被称为递归可枚举。

而如果存在一个图灵机招募 L 的所有成员并在 L 的每个成员上停止作为输入，则称 L 是递归的。

因此，从上面的陈述中可以清楚地看出，每种递归语言也是递归可枚举的，但反之则不然。

下面给出了语言家族之间的确切联系。

定理

步骤 1 - 当且仅当 L 及其相对于 T* 的补码 L 都是递归可枚举的，才称语言 L 在字母 T 上递归。
步骤 2 - 语言 L^(R) 的反转是由 T* 的所有元素串组成的集合，我们可以通过以相反的顺序编写 L 的所有元素来获得。
第 3 步- 让我们考虑一种可递归枚举的语言 L，其所有元素都由图灵机 M 登记。
第 4 步- 我们现在可以设计另一个图灵机 M'，其字符串被接受为 L 成员的反向字符串。
第 5 步- 这也符合教堂图灵论文，该论文指出，某些图灵机也可以完成每个有效的计算过程
第 6 步- 从上面的讨论可以清楚地看出，L 是递归可枚举的，而不是它的反转 L^(R) 也是递归可枚举的。
步骤 7 - 如果 T* 的字符串 X 在 (L^(R))' 中，当且仅当 X 不是 L^(R) 这清楚地意味着当且仅当 X^(R) 的反转不属于到 L，这进一步暗示 X^(R) 属于 L'⇔ X 属于 l^(R)。
即 (L^(R))' = L'^(R)

结论

如果 L 是递归的，那么 L'(R) 及其补码 (L^(R))' 也是递归可枚举的，这进一步意味着 L^(R) 的反转也是递归的。