一些一般类型的问题

第4.1节介绍了语言的几个大类。我将在这里快速概述一下这些类。

第一类问题是接受问题：给定一台机器的描述 和一个输入字符串x，机器是否接受它的输入？根据机器的类型，这类问题分为ADFA、APDA和ATM等子类。

第二类问题是空性问题：给定机器 的描述，我们必须确定机器是否不接受它的任何输入。这类问题分为EDFA、EPDA和ETM等子类。

第三类问题是等式问题：给定两台机器 和 的描述，我们必须确定两台机器是否接受相同的语言。这类问题分为EQDFA、EQPDA和EQTM等子类。

解决其中的一些问题

下面的五个小节将展示这类问题的五个示例。我要展示的每一个例子都是由图灵机决定的。在每种情况下，我都会给出语言的描述，然后是决定语言的图灵机的描述。

一个DFA

ADFA = {<,w> | 描述DFA A， A接受w}

输入<<A>,w>：

  1. 模拟w在A上运行。
  2. 如果A接受w，接受；否则,拒绝。

EDFA

EDFA = { | 描述一个DFA A， A不接受输入}

当输入<A>时：

  1. 如果A的起始状态为接受状态，则停止并拒绝。
  2. 标记A的开始状态。
  3. 重复，直到没有新的状态可以标记：
    1. 找到从标记状态到未标记状态的转换。
    2. 标记未标记的状态。
    3. 如果您刚刚标记的状态是接受状态，请停止并拒绝。
  4. 停下来接受。

情商DFA

EQDFA = {<,> | 描述DFA A，描述DFA B， A和B接受相同的语言。｝

两个集合X和Y的对称差是(X∩Y)∪(Y∩X)。

当输入<<A>,<B>>时：

  1. 构造一个接受集合L(A)和L(B)的对称差的机器。
  2. 运行E的算法DFA在这台机器上，并返回它所做的。

一个CFG

ACFG = {< ,w> | 为CFG， w为字符串，G生成w}

当输入<<G>,w>时：

  1. 将G转换为乔姆斯基范式G．
  2. 生成G的赢博体育导数产生长度≤|的字符串w|。
  3. 如果w是这些推导的结果，停止并接受。
  4. 否则，停止并拒绝。

ECFG

ECFG = { | 是一个不生成字符串的CFG。｝

当输入<G>时：

  1. 如果语法包含任何规则，其右侧仅包含终结符，则在该规则的左侧标记变量。
  2. 重复，直到没有新的变量可以被标记：
    1. 如果语法包含任何规则，其右侧的符号都已被标记，则在规则的左侧标记变量。
  3. 如果已标记开始符号，请停止并拒绝。
  4. 否则，停止并接受。

可决定和不可决定的问题

下表总结了第4章和第5章的主要结果。第4.1节介绍了可用于解决这些问题的算法，而第4.2节和第5章的部分内容则证明了这些问题中的其他问题不能由任何算法决定。

问题 DFA 掌上电脑 TM
一个 可决定的 可决定的 不可判定的
E 可决定的 可决定的 不可判定的
情商 可决定的 不可判定的 不可判定的

通用图灵机

在第3.2节的课堂笔记中，我提到了通用图灵机的概念。这是一种图灵机，它可以将任何其他图灵机的描述作为输入，并附带一个输入字符串x。通用图灵机可以读取这个输入，然后在其他机器上模拟输入字符串的运行。

一旦我们确定了这样一台机器的存在，我们就可以自由地在我们建造的其他机器中使用这台机器作为子程序。因此，下面描述的许多机器都具有我们模拟在另一台机器上运行输入的步骤。从这一点开始，这将永远被认为是图灵机的一个合法步骤。

第一种无法确定的语言

教材在4.2节中给出了ATM问题不可判定的证明。作者使用的策略是假设问题是可决定的，然后表明这个假设导致矛盾。我鼓励你们读一读这个证明。

为了多样化，我将对计算理论中的另一个重要问题——停止问题——提出一个类似的证明。图灵机的一个独特之处在于它们有能力陷入无限循环。这意味着某些机器在给定特定输入时永远不会停止工作。这就变成了一个普遍的问题，叫做停止程序。给定任意图灵机 和任意输入w的描述，确定在给定此输入时，机器M最终是否会停止在接受或拒绝状态。

证明开始于假设有一台图灵机H可以解决停机问题。然后我们在几个步骤中产生一个矛盾。

首先，我们构造下面的机器D。

对于任何 的输入：

  1. 在输入对 , 上运行H。
  2. 如果H接受，则进入无限循环并永远运行。
  3. 否则，停止并接受。

当我们在输入< d>上运行D时，矛盾就出现了。

如果H预测D会在按照自己的描述运行时停止，那么D会继续运行并永远运行下去。

如果H预测D在按照自己的描述运行时将永远运行，则D停止。

在这两种情况下，D表现出的实际行为都与H预测的相反。这是一个矛盾。解决这一矛盾的唯一方法是放弃我们最初的假设，即停止问题是可决定的。