减少$ l_c={\ langle m_1 \ rangle，\ langle m_2 \ rangle）：l（m_1）\ cap l（m_2）\ neq \ imptyset \} $ to $ a_ {tm} $

Question

如何减少 $ l_c={\ langle m_1 \ rangle，\ langle m_2 \ rangle）：l（m_1）\ cap l（m_2）\ neq \ imptyset \} $ 到 $ a_ {tm}={\ langle m，w \ rangle：m $ 是一个接受 $ W $ }。

我的尝试： 构建一个图灵类=“math-container”> $ n $ 使用图灵类 $ u $ ，使普通语言作为子程序决定 $ l_c $ 。 $ n $ ，在任何输入 $ <\ langle m_1 \ rangle，\ langle m_2 \ rangle> $ ：
$ 1。$ 构造一个程序，该程序在规范顺序中生成Word $ w \ in \ sum ^ \ ast $ 。
$ 2。$ 运行 $ u $ 上 $ \ langle m_1 ，w \ rangle $ 和 $ \ langle m_2，w \ rangle $ 。
$ 3。$ 如果 $ u $ 接受两者，接受。
$ 4。$ 如果没有，返回 $ 1 $ 。

似乎不起作用。因为如果 $ l（m_1）\ cap l（m_2）=imptyset $ ， $ n $ 将永远循环（它只是找不到这样的 $ w $ ）。

Answer 1

您询问的减少方向有点奇怪。通常，我们从 $ a__ {tm} $ ，以便显示未索引。

也许你的意思是询问另一个方向？

以任何速度，在答案到您的问题：您的尝试实际上非常接近，它只需要一些修改。以下是如何继续的：

给定 $ m_1，m_2 $ 作为 $ l_c $ 的输入，构造一个新的机器 $ n $ 工作如下：给定输入 $ x $ ， $ n $ 忽略它（即，删除 $ x $ 从它的磁带），然后开始模拟 $ m_1 $ 和 $ m_2 $ 在每个字 $ w \ in \ sigma ^ * $ ，在规范秩序中。但是，注意，为了模拟 $ m_1 $ 和 $ m_2 $ 上的所有< / EM>单词，我们不能简单地任意在每个单词上运行它们，因为我们可能被困（我们不使用Oracle到 $ A_ {TM} $ ）。相反，我们在并行中运行它们：运行 $ m_1 $ 和 $ m_2 $ 在 $ k $ $ \ sigma ^ * $ for $ k $ 步骤，然后增加 $ k $ by 1.这是一个相当普遍的技巧，但它非常聪明。

现在，如果在任何点 $ m_1 $ 和 $ m_2 $ 接受，那么 $ n $ 接受。否则，它会导致运行和增加 $ k $ 永远。

通过发送 $ $ 到 $ a_ {tm} $ < / span> Oracle（或者，如果将其视为映射减少，则完成它是完整的）。

注意， $ n $ 接受 $ \ epsilon $ （以及任何其他单词）IFF有a由 $ m_1 $ 和 $ m_2 $ 。