如果我们有两个描述可判定语言的TM，那么等价问题仍然是不可判定的吗？
在计算复杂性理论领域，可判定性概念起着根本性的作用。如果存在一个图灵机 (TM)，能够确定任何给定输入是否属于该语言，则该语言被称为可判定的。语言的可判定性是一个重要属性，因为它使我们能够以算法方式推理语言及其属性。
图灵机的等价问题涉及确定两个给定的 TM 是否识别相同的语言。 形式上，给定两个 TM M1 和 M2，等价问题询问是否 L(M1) = L(M2)，其中 L(M) 表示 TM M 识别的语言。
已知确定两个 TM 等价性的一般问题是不可判定的。 这意味着没有任何算法可以始终确定两个任意 TM 是否识别相同的语言。 艾伦·图灵在其关于可计算性的开创性工作中证明了这一结果。
然而，值得注意的是，这个结果适用于任意 TM 的一般情况。 在两个 TM 都描述可判定语言的特定情况下，等价问题变得可判定。 这是因为可判定语言是那些存在可以决定该语言成员资格的 TM 的语言。 因此，如果两个 TM 描述了可判定的语言，我们可以构造一个新的 TM 来决定它们的等价性。
为了说明这一点，让我们考虑一个例子。 假设我们有两个描述可判定语言的 TM M1 和 M2。 我们可以构造一个新的 TM M 来决定它们的等价性，如下所示：
1. 给定输入 x，同时在 x 上模拟 M1 并在 x 上模拟 M2。
2. 如果M1接受x并且M2接受x，则接受。
3. 如果M1拒绝x并且M2拒绝x，则接受。
4. 否则，拒绝。
通过构造，当且仅当 M1 和 M2 都接受 x，或者 M1 和 M2 都拒绝 x 时，TM M 才会接受输入 x。 这意味着对于任何给定的输入 x，M 决定 M1 和 M2 的等价性。
虽然确定两个任意 TM 的等价性的一般问题是不可判定的，但如果 TM 描述可判定的语言，则等价问题就变得可判定。 这是因为可判定语言可以由 TM 决定，从而允许我们构造一个 TM 来决定它们的等价性。 描述可判定语言的 TM 等价问题的可判定性为这些语言的计算复杂性提供了重要的见解。
最近的其他问题和解答 可判定性:
- 磁带是否可以限制为输入的大小（这相当于图灵机的头部被限制在 TM 磁带的输入之外移动）？
- 不同版本的图灵机在计算能力上是等效的意味着什么？
- 图灵可识别语言能否形成可判定语言的子集？
- 图灵机的停机问题是可判定的吗？
- 线性有界自动机的接受问题与图灵机的接受问题有何不同？
- 给出一个可以由线性有界自动机决定的问题的例子。
- 在线性有界自动机的背景下解释可判定性的概念。
- 线性有界自动机中带子的大小如何影响不同配置的数量？
- 线性有界自动机和图灵机之间的主要区别是什么？
- 描述将图灵机转换为 PCP 的一组图块的过程，以及这些图块如何表示计算历史。