“有问题”图灵机的非暂停输入

Question

让我们启动这个问题，通过定义图灵机来定义它的单词并不停止。 定义： $ p（m）={w \ in \ sigma ^ * | m $ 在 $上没有停止w \} $

我们知道 $ halt $ 问题是 $ re \ setminus r $ - 因此每个tm $ m $ 计算 $ halt $ 有一个单词它不会停止，即 $ P（M）\ ne \ nem \ imptyset $ 。

从此，出现（简单）问题：

$ q（1）：$ “是一个问题，如果只有计算它的每个TM，它具有非空的'有问题'set $ p（m）$ ？“ $ ^ {q \ space（1）} $

此外，让我们注意到，对于 $ halt $ 问题，我们知道给定 $ m $ 计算它，无数的输入，它永远不会停止（我鼓励为什么这是如此，在帖子中进行之前）

所以，同样，我们可能想问我们自己的（略显更加困难的第一个问题。

$ q（2）：$ “是一个问题未定定的iff，每个tm $ m $ 计算它具有 $ | p（m）|=aleph_0 $ ？“ $ ^ {q \ space（2）} $

而且，我们问一个更强大的问题：

$ q（3）：$ “如果 $ l $ 未定定，我们仍然存在能够找到有限的设置的图灵机 $ m_1，...，m_n $ compute $ l $ ，并且具有 $ \ bigcap_ {k \ space= space0} ^ np（m_k）$ 有限？一个无限一套满足这一点的图灵机？“ $ ^ {q \ space（3）} $

和我们的最终（半公开）问题将是：

$ q（4）：$ “我们还能理解图规定机器及其有问题的集合吗？”

Answer 1

所以，让我们开始解决这些问题。作为一个侧面笔记，我安排了这些问题，使得每个问题使用它之前的答案（以这种方式，它们几乎似乎太微不足道，以便以 $：$ p）。

$ a（1）：$ 从定义非常微不足道。如果 $ l $ 未定义，则没有计算它，并且始终停止，因此所有图灵计算机都计算 $ l $ 具有 $ p（m）\ ne \ nem \ namsets $ 。 另一个方向也像这个一样简单。

$ a（2）：$ 让我们假设 $ l $ 是不可行的。如果有一个图灵机 $ m $ 计算 $ l $ 并且有一个有限的 $ P（m）$ ，然后让我们构建一个新的机器 $ \ hat m $ ，使其将具有 $ p（\ hat m）=imptyset $ 如下所示（在输入 $ w $ ）：

• 拒绝（如果 $ w \以p（m）$ ）（因为 $ p（m）$ < / span>是有限的）
否则，返回 $ m（w）$

这款新机器，将停止每个 $ w \以p（m）$ ，但由于每个 $ w \ notin p（m）$ 它将运行 $ m $ ，它保证它将停止它（因为否则它会在 $ p（m）$ ），我们有新的 $ \ hat m $ 始终停止，接受 $ l $ - 因此相矛盾。另一个方向只是衍生自 $ a（1）$ 。

$ a（3）$ ：对于有限设置的图灵机， $ m_1 ，... M_N $ 我们将表明它不可能拥有有限的 $ \ bigcap_ {k \ space= space0} ^ np（m_k）$ 但是未定定的 $ l $ 。让我们假设这不矛盾。刚刚在 $ a（2）$ 时，我们将构建 $ \ hat m $ - 但现在它足够了要构建它，这样<跨越类=“math-container”> $ p（\ hat m）=bigcap_ {k \ space= space0} ^ np（m_k）：$

• 运行 $ m_1（w），m_2（w），...，m_n（w）$ 在并行
• 接受其中任何一个接受。

现在，显而易见的为什么 $ \ hat m $ 接受 $ l $ 。让 $ w \ notin p（\ hat m）$ ，然后有一些 $ 1 \ le k \ le n $ < / span>这样<跨越类=“math-container”> $ m_k（w）$ 停止，因此 $ w \ notin \ bigcap_ {k \ space=space0} ^ np（m_k）$ 。让 $ w \在p（\ hat m）$ 中，然后它在任何 $ m_k $ ，因此 $ w \以p（m_k）$ 为所有 $ k $ 。结论是<跨越类=“数学容器”> $ p（\ hat m）=bigcap_ {k \ space=space0} ^ np（m_k）$ 是有限的，因此来自 $ a（2）$ 不能存在。

关于无限的设置的图灵机，这绝对可能。只是为每个 $ w \ in \ sigma ^ * $ 机器 $ m_w $ 接受 $ l $ ，但也会停止 $ w $ （类似于 $ a（2）$ ）。然后 $ w \ notin p（m_w）$ 因此 $ w \ notin \ bigcap _ {\ hat w} p（m_ \帽子w）$ ，因此不仅是 $ \ bigcap _ {\ hat w} p（m_ \ hat w）$ 是有限的，它也是空的。

$ a（4）：$ let $ l $ 不可确定， $ M_1，M_2 ... $ 是接受 $ l $ 及其对”有问题集“的交点是有限的。如果我们查看函数 $ f：\ mathbb {n} \ lightarrow \ sigma ^ * $ 由 $ f（ k）=langle m_k \ rangle $ ，那么它是 not compualable。这是从 $ a（2）$ 之后，因为该函数可计算，我们可以创建一个图灵机 $ \ hat m $ 带

ontainer“> $ p（\ hat m）=bigcap_k p（m_k）$

我已经开始思考的另一个想法是在我们谈论两个语言或更多时，而不是一个时会发生什么。让 $ m_1 $ 为 $ l_1 $ 和 $ m_2 $ $ l_2 $ 。然后，我们可以定义一个机器 $ m $ for $ l_1 \ bigcap l_2 $ 或 $ l_1 \ bigcup l_2 $ with：

$ p（m）= p（m_1）\ bigcup p（m_2）$ （注意事项也可以在 $ \ mathcal r $ ）

或if $ l_1 \ delta l_2 $ 是有限的，那么我们的语言的有问题的机器都相同（对于每台机器 $ M $ 在其中任何一个中，我们可以找到机器 $ m'_1，m'_2 $ 其他两个语言具有相同的问题集）

虽然我还没有写上述正式证据。 （老实说，我没有能量写出更多类似的证据，在这一篇大帖子中）我仍然鼓励你在家里证明它！

最后！我认为（但仍然不确定）我们可以在时间复杂性分析时获得类似的结果（但有更多的约束）如果我们定义 $ p（m，t）$ 时间 - 构造 $ t（n）\ ge log（n）$ 作为单词组 $ m $ nonn在 $ t（n）$ 步骤中停止。在这个定义中，常量存在棘手的问题，因此通过定义新机器更难地显示定理（因为它们可能会做一些更加持续的工作，这将使一些单词进入有问题的集合，并且这里的大o表示法对于不同常数有些毫无意义）

如果您认为某些东西不正确，或者只想添加更多 - 我很乐意进行更改。