本文概述
- 通用语言的不确定性
通用语言的不确定性【介绍不可判定性】通用语言Lu是一种可递归枚举的语言，我们必须证明它是不确定的（非递归）。
定理：Lu是RE，但不是递归的。
证明：
考虑到Lu是递归可枚举的语言。我们将假定Lu是递归的。那么Lu的补语L’ u也是递归的。但是，如果我们有一个TM M接受L`u，那么我们可以构造一个TM Ld。但是，对角化语言不是RE。因此，我们关于Lu是递归的假设是错误的（不是RE表示不是递归）。因此我们可以说Lu是RE，但不是递归。 L的M的构造如下图所示：
文章图片
