本文概述
在计算理论中,我们经常遇到这样的问题,这些问题回答为“是”或“否”。可以回答“是”的问题类别称为可解决的或可判定的。否则,这类问题被认为是无法解决或无法确定的。
通用语言的不确定性
通用语言Lu是一种可递归枚举的语言,我们必须证明它是不确定的(非递归)。
定理:Lu是RE,但不是递归的。
证明:
考虑到Lu是递归可枚举的语言。我们将假定Lu是递归的。那么Lu的补语L’u也是递归的。但是,如果我们有一个TM M接受L`u,那么我们可以构造一个TM Ld。但是,对角化语言不是RE。因此,我们关于Lu是递归的假设是错误的(不是RE表示不是递归)。因此我们可以说Lu是RE,但不是递归。 L的M的构造如下图所示:
评论前必须登录!
注册