不可判定性的介绍

在计算理论中，我们经常遇到只能回答“是”或“否”的问题。 可以回答“是”的一类问题称为可解或可判定的。 否则，该类问题被称为不可解或不可判定的。

通用语言的不可判定性

通用语言 L_u 是一种递归可枚举语言，我们必须证明它是不可判定的（非递归的）。

定理： L_u 是 RE 但不是递归的。

证明

考虑语言 L_u 是一种递归可枚举语言。我们将假设 L_u 是递归的。那么 L_u 的补集 L`u 也是递归的。 但是，如果我们有一个 TM M 来接受 L`u，那么我们可以构造一个 TM L_d。 但是 L_d 对角化语言不是 RE。 因此，我们假设 L_u 是递归的是错误的（不是 RE 意味着不是递归的）。 因此，我们可以说 L_u 是 RE 但不是递归的。 L_d 的 M 的构造如下图所示