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

关于图灵机的无法确定的问题

本文概述

在本节中,我们将讨论有关图灵机的所有不确定的问题。减少量用于证明给定语言是否可取。在本节中,我们将首先了解归约的概念,然后我们将在这方面看到一个重要的定理。

减少

归约是一种技术,其中,如果将问题P1简化为问题P2,则任何P2的解决方案都可以解决P1。通常,如果我们有一种算法可以将问题P1的实例转换为具有相同答案的问题P2的实例,则将其称为P1简化P2。因此,如果P1不是递归的,则P2也不是递归的。同样,如果P1不可递归枚举,则P2也不可递归枚举。

定理:如果将P1简化为P2,则

  1. 如果P1不确定,则P2也是不确定的。
  2. 如果P1是非RE,则P2也是非RE。

证明:

  1. 考虑P1的实例w。然后构造一个算法,使该算法将实例w作为输入并将其转换为P2的另一个实例x。然后应用该算法检查x是否在P2中。如果算法回答“是”,则意味着x在P2中,类似地,我们也可以说w在P1中。由于我们在还原P1之后获得了P2。同样,如果算法回答“否”,则x不在P2中,这也意味着w不在P1中。这证明了如果P1不可确定,则P1也是不可确定的。
  2. 我们假设P1是非RE,但P2是RE。现在构造一个将P1减少到P2的算法,但是通过该算法,P2将被识别。这意味着如果输入为P2,将会有一个图灵机说“是”,但是对于不在P2中的输入,可能会或可能不会停止。众所周知,可以将P1中w的实例转换为P2中x的实例。然后应用TM检查x是否在P2中。如果x被接受,那也意味着w被接受。如果w在P1中,则x也在P2中,如果w在P1中,则x也不在P2中,此过程描述了一个语言为P1的TM。这证明了如果P1是非RE,那么P2也是非RE。

空和非空语言

有空和非空两种语言。令Le表示空语言,而Lne表示非空语言。令w为二进制字符串,Mi为TM。如果L(Mj)=Ф,则Mi不接受输入,则w在Le中。同样,如果L(Mj)不是空语言,则w用Lne表示。因此我们可以说

Le = {M | L(M)=Ф} Lne = {M | L(M)≠Ф}

Le和Lne互为补充。


赞(0) 打赏
未经允许不得转载:srcmini » 关于图灵机的无法确定的问题
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

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

微信扫一扫打赏