我试图证明 TM = DFA 使用停止问题的减少是不可判定的 理论上我知道图灵机捕获所有可计算的函数，而 DFA 只捕获可以在恒定空间中计算的函数，因此 TM = DFA 是不可判定的。
这是我的步骤：假设决定 L(M)=L(D) 的 R
EQ_DM = { [D,M] | L(M) = L(D) }
我们创建了一个图灵机
HALT_TM = { [M,w] | （M 在输入 w 时停止→接受
M 在输入 w 时没有停止→拒绝）}
我如何构造一个 D & M 以便 R[D,M] 告诉 M 是否在 w 上停止？
假设 TM 和 DFA 是否接受相同的语言是可判定的。您可以使用它来解决一般 TM 的停止问题。
给定任何 TM M 和单词 w，构造 M' 使得每当 M 进入停止拒绝状态时，M' 进入停止接受状态。现在，M' 是一个 TM，它接受导致 M 停止的每个字符串。现在从 M' 构造 M'' 使得 L(M'') 是 L(M') 和 {w} 的交集，其中 w 是任何单词。在给定 {w} 和 M' 的 DFA 的情况下，您始终可以使用笛卡尔积机器构造来构造 M''。
由于可以确定 L(M'') 是否等于 DFA 的 DFA - 例如 {w} 的 DFA - 我们可以说 M'' 是否接受 {w}。如果它接受 w，则 L(M') 包含 w，如果 L(M') 包含 w，则 M 在 w 上停止。如果 M'' 不接受 w，则 L(M') 不包含 w，因此，M 不会在 w 上停止。