证明递归语言集在反转下是封闭的？
考虑语言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)的反转也是递归的。