帮助在参数中查找缺陷，模拟具有较小的大型图灵机

cs.stackexchange https://cs.stackexchange.com/questions/121911

  •  29-09-2020
  •  | 
  •  

题

我有一个论点，如果它经过，只是证明了：

  • 编程语言比图灵机更强大
  • TULE机器上的BUSY BEAVER函数（ $ bb（）$ ）是可计算

现在，我明白，我的论点更有可能有一些我找不到的缺陷。但对我来说，如何我错了，而不是是否出现了。

参数

构造一个图定机 $ m_1 $ ，它作为参数（在磁带上） $ n，k $ < / span>，模拟所有带有 $ n $ 状态，直到 $ k $ 它们的暂停，然后停止自己。这很容易以编程语言编写，如以下Python Snippet所示：

def M1(n, k):
    all_machines = generate_turing_machines(n)
    is_halted = [0] * len(generate_turing_machines)
    while sum(is_halted) < k:
        for (i, machine) in enumerate(all_machines):
            machine.step()
            if machine.is_halted():
                is_halted[i] = 1
.

现在，让 $ m_1 $ 是 $ m_1 $ 所需的状态数。修复 $ n $ 大于 $ m_1 $ 。让 $ k_1 $ 是最大的数字，使得 $ m_1（n，k_1）$ halts和 $ k_0 $ 是最小的数字，使得当 $ m_1（n，k_0）$ 停止时， $ K_1 $ 模拟图灵机已停止（因为所有等效机器将在同一步骤停止）。选择 $ k $ 使用 $ k_0 \ leq k \ leq k_1 $ 。这意味着 $ m_1（n，k）$ 停止在约 $ bb（n）$ 步骤中。

构造 $ m_2 $ 与 $ m_1 $ 除了它的第一件事之外写入 $ n $ 和 $ k $ 到磁带。让 $ m_2 $ 是 $ m_2 $ 所需的状态数。然后 $ m_1 + k（n）+ k（k）+ c= m_2 $ 对于一些小 $ c $ （可能是恒定的，可能是 $ 0 $ ），其中 $ k（n）$ 是 $ n $ 在图灵机状态下的Kolmogorov复杂性。

现在， $ k（n）$ 是大多数 $ o（\ log（n））$ 。关于 $ n ^ n $ machines，带 $ n $ 状态，因此 $ k $ 是关于 $ n ^ n $ ，因此 $ k（k） $ 最多是 $ o（\ log（n ^ n））= o（n \ cdot \ log（n））$ 。这意味着 $ m_2> n $ 。但是在这里我们有一个问题：如果 $ k $ 更容易写入磁带（因此 $ k（k） ），然后 $ m_2 $ 将略小于 $ n $ 。这将意味着 $ bb（m_2）> bb（n）$ 和 $ m_2 ，a清晰的矛盾。

在我的脑海里，这些是可能的解决方案：

  • $ m_1 $ 无法创建为图定机器，这意味着Python比图灵机更强大。
  • 有一些Transfinite延伸到图灵的机器通常比图灵机更强大，而 $ M_1 $ 可以写入此扩展名。换句话说， $ m_1 $ 是一组机器的限制 $ m_ {1，n} $ ，每个每个可以处理任何 $ n 。这可能需要繁忙的海狸功能可计算。
  • 有一大组数字，不能在少于 $ \ log（k）= n $ 状态（我们需要< SPAN Class=“math-container”> $ k（k））。我似乎不可能为 $（n，k）$ 的候选人可以充分压缩。

此逻辑中的错误在哪里？

我之前说过 $ k（k）\ leq o（n）$ ，但@ 6005指出嫌疑人。用这个固定（到 $ o（n \ cdot \ log（n））$ ），对我来说仍然非常令人惊讶，我们无法达到减少 $ k（k）\约n \ cdot \ log（n）$ <

/ span>到 $ k（k）对于 $（n，k）$ ，但不再是不可思议的。
有帮助吗？

解决方案

你的缺陷似乎在这里：

现在， $ k（n）$ 是大多数 $ o（\ log（n））$ 。 $ k $ 是关于 $ n ^ n $ ，因此 $ k（k）$ 最多 $ o（n）$ 。将 $ m_2 $ 略大于 $ n $ 。

是如此， $ k $ 是关于 $ n ^ n $ （更准确地说， $ k= n ^ {\ theta（n）} $ 或 $ k= 2 ^ {\ theta（n \ log n） $ ，这可以通过上限 $ k $ 通过查找简单暂停图灵的家庭来显示机器）。但是，这并不意味着<跨度类=“math-container”> $ k（k）$ 是大多数 $ o（n）$ 。 相反，我们只知道 $ k（k）$ 最多 $$ o（\ log（n ^ n））= o（n \ log n）。 $$

您的矛盾依赖于拣选 $ k $ 使 $ k（k）$ 是 $ o（n）$ （比 $ n $ ）。你的推理表明这是不可能的。

但这并不令人惊讶：大多数 $ k $ 我们希望是 $ o（n \ log n ）$ ，和 $ k $ 是一个数字，其中包含有关带有 $ n的图灵机的大量信息$ 状态，所以我们不希望能够压缩这样的数字，小于 $ o（n）$ 状态。

ps 放置Python是否真的等同于图灵机的问题（可能没有人知道，只要它尚未正式显示），您的程序生成icotagcode实际上是清楚地表示的图灵机。由此，您应该能够看到基于M1的分辨率不可表示为图定机器不正确。

许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top