使用暂停语言，证明$ e_ {tm} $

Question

如何证明：

$ e_ {tm}={\ langle m \ rangle \ mid m \是\ a \ tm \ and \ l（m）=imptyset \} \ notin r$ （不可确定）

使用语言：

$ h_ {halt}={（⟨m⟩，w）：m \ halts \ in \ w \} $ 。

我试图通过矛盾证明 $ e_ {tm} \在r $ 中，我有一个图灵的机器，它决定 $ e_ {tm} $ 并用它用它来构造一个图灵的机器，它决定 $ h_ {halt} $ 但我不知道该怎么办所以。

Answer 1

假设有一个图灵机 $ t $ ，它决定 $ e_ {tm} $ 。

给定转动机 $ m $ 和输入 $ w $ 您可以构建新的图灵machine $ m ^ * $ ，它决定 $（m，w）\中的h_ {halt} $ 。 $ m ^ * $ 按如下方式运行：

• 首先构建一个新的图灵机 $ m'$ 忽略它的输入，模拟 $ m $ 在输入 $ w $ ，并且一旦模拟完成，接受。
• 它模拟 $ t $ 使用输入 $ m'$ 来决定中的数学集装箱“> $ m'\。
• 如果 $ m'\在e_ {tm} $ 中，则 $ m'$ 不接受任何输入，这意味着 $ m $ 无法在输入 $ w $ 上。在这种情况下 $ m ^ * $ 拒绝。
• 如果 $ m'\在e_ {tm} $ 中，则 $ m'$ 至少接受一个输入（并因此输入所有输入），这意味着 $ m $ 必须停止输入 $ w $ 。在这种情况下 $ m ^ * $ 接受。

Answer 2

你是对的，假设 $ e_ {tm} \以$ 为您具有图灵机 $ t $ ，它决定 $ e_ {tm} $ ，您可以使用它来构造，是一个图灵的机器，它决定< SPAN Class=“Math-Container”> $ H_ {HALT} $ ：

如果我们有 $ t $ ，它会决定 $ e_ {tm} $ 并假设我们想要决定是否<跨越类=“math-container”> $ m $ 停止 $ x $ 。 构造一个图灵机 $ t_ {m，x} $ ，无论其输入 $ y $ 模拟< Span Class=“Math-Container”> $ M $ On Input $ x $ ：如果模拟停止（和 $ M $ 接受或拒绝 $ x $ ），然后 $ t_ {m，x} $ 接受其输入，否则，它永远不会停止。

你可以说服自己，如果 $ m $ 停止 $ x $ ，则 $ l（t_ {m，x}）=sigma ^ * $ ，如果它没有 $ l（t_ { m，x}）=phi $ 。

现在你可以弄清楚为什么这充当逐渐减半问题的决策者。