computer-science - 不经意间的图灵机是如何工作的？

Question

我正在阅读《计算复杂性：一种现代方法》一书，但在理解遗忘的图灵机时遇到了问题。

不经意的图灵机 (TM) 就是这样一种 TM，其头部的运动完全由输入的长度决定。也就是说，TM 忽略了它的输入。到目前为止，一切都很好。

但其中一项练习是证明以下定理：

If a language L is decidable in time T(n) 
then there exists an oblivious TM that decides L in time O(T(n)^2).

很明显，不经意的 TM 不能对原始输入进行操作，L而是在某个编码版本上操作。也就是说，该定理的要点是将位串编码为整数（遗忘 TM的输入长度）。但是，如果想要将 (bitstrings) 的一组可能输入编码为整数，那么由于存在length的位串，因此会很快遇到非常高的数字。L2^nn

我是否正确理解了这个问题？你如何证明这个定理？

score 7 · Accepted Answer

在这里，我建议你阅读这篇论文。这是一篇相当有趣且精彩的论文，它将在要求的较低时间范围内为您提供证明。（我认为您应该能够将其定义为 O(N^2) 或者您可以得出结论 O(N*log(N)) 在技术上是 O(N^2) 但直接遵循这个证明可能会让您的教授感到不安。我想他打算让你以不同的方式处理它。

编辑：

该论文的原始链接不再有效。这是另一个公开发布的。

“复杂性度量之间的关系”，Michael J. Fischer 和 Nicholas Pippenger，1979 年。

1 回答 1