个性化阅读
专注于IT技术分析

介绍不可判定性

本文概述

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

通用语言的不确定性

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

定理:Lu是RE,但不是递归的。

证明:

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


赞(0) 打赏
未经允许不得转载:srcmini » 介绍不可判定性
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏