介绍不可判定性

本文概述

• 通用语言的不确定性

在计算理论中，我们经常遇到这样的问题，这些问题回答为“是”或“否”。可以回答“是”的问题类别称为可解决的或可判定的。否则，这类问题被认为是无法解决或无法确定的。

通用语言的不确定性

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

定理：Lu是RE，但不是递归的。

证明：

考虑到Lu是递归可枚举的语言。我们将假定Lu是递归的。那么Lu的补语L’u也是递归的。但是，如果我们有一个TM M接受L`u，那么我们可以构造一个TM Ld。但是，对角化语言不是RE。因此，我们关于Lu是递归的假设是错误的（不是RE表示不是递归）。因此我们可以说Lu是RE，但不是递归。 L的M的构造如下图所示：