构造一个图灵机，该机器决定固定的TM是否会在固定输入上停止

Question

它是已知暂停问题对于每个固定的 $ m_0 $ 图灵机和每个固定的 $ w_0 $ 输入。

我的相关问题是以下内容：对于每个固定的 $ m_0 $ 图灵机和每个固定的 $ w_0 $ 输入，AN $ M_ {M_0，W_0} $ 图灵机可以构造，可能的输入是 $（m，w）$ 机器输入对，以及 $（m_0，w_0）$ 对，输出为”1 “如果 $ m_0 $ 将停止在 $ w_0 $ 和”0“，如果 $ M_0 $ 将不会停止 $ w_0 $ ？ （ $ m_ {m_0，w_0} $ 可以给出其他对的错误答案，但不要求它必须正确运行每个 $（m，w）$ 配对。）

Answer 1

自 $ m_0 $ 和 $ w_0 $ 是问题的问题，答案是肯定的：对于每个固定的 $ m_0 $ 和 $ w_0 $ ，存在一个图灵机 $ M_ {M_0，W_0} $ （取决于 $ m_0 $ 和 $ w_0 $ ）这样，对于输入 $（m_0，w_0）$ ， $ m_ {m_0，w_0 $ 返回 $ 1 $ 如果 $ m_0（w_0）$ 停止和0否则。< / p> 特别是一个这样的图灵机 $ m_ {m_0，w_0} $ 必须是以下两台机器之一：

• $ m'_1 $ ：write $ 1 $ 。停止。
• $ m'_0 $ ：write $ 0 $ 。停止。

如果代替，您正在寻找一种算法，它需要 $ m_0 $ 和 $ w_0 $ 作为输入和输出机器 $ m_ {m_0，w_0} $ 使用上述属性，那么您正运行运气：常规没有这样的算法（它可能存在如果限制输入机器集 $ m_0 $ ）。 假设这样的算法（即，图测机器） $ a $ 存在，那么它将允许解决停止问题：

给定 $ m_0 $ 和 $ w_0 $ ，compute $ m_ {m_0，w_0} $ 通过模拟 $ a $ 在输入 $（m_0，w_0）上$ 。
• 模拟 $ m_ {m_0，w_0} $ 在输入 $（m_0，w_0）$ 上。根据 $ m_ {m_0，w_0} $ 此步骤需要有限时间。
• 如果 $ m_ {m_0，w_0}（（m_0，w_0））$ 是 $ 1 $ ，否则返回“否”。