证明TM和DFA的等价性

Question

我试图用停止问题的减少来证明TM = DFA是不可判定的理论上我明白图灵机捕获所有可计算函数，而DFA只捕获可以常量计算的函数因此TM = DFA是不可判定的。

这里是我的步骤： 假设是R那个决定L（M）= L（d）

EQ_DM = {[d，M] | L（M）= L（d）}

和我们创建一个图灵机

HALT_TM = {[M，W] | （在输入砂→M停止接受
中号没有输入停止波→拒绝）}

如何构建一个d &中号中以r [d，M]告诉如果M停止W上？

Answer 1

假设TM和DFA是否接受相同的语言是可判定的。您可以使用它来解决一般TM的停机问题。

给定任何TM M和单词w，构造M'，以便每当M进入暂停状态时，M'进入暂停接受状态。现在，M'是一个接受导致M停止的每个字符串的TM。现在从M'构造M“，使得L（M”）是L（M'）和{w}的交点，其中w是任何单词。给定{D}和M'的DFA，您可以始终使用笛卡尔产品机器构造来构造M''。由于可以确定L（M“）是否等于DFA的值 - 比如说{W}的DFA，我们可以说M''是否接受{w}。如果它接受w，则L（M'）包含w，并且如果L（M'）包含w，则M将停止在w上。如果M“不接受w，则L（M'）不包含w，因此M不会停止w。