Mar*_*dik 9 computer-science turing-machines
我正在阅读" 计算复杂性:现代方法"这本书,我在理解不经意的图灵机时遇到了问题.
不经意的图灵机(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的输入的长度).但是如果想要将L(位串)的可能输入集合编码为整数,则由于存在2^n长度的位串,因此会很快地遇到非常高的数字n.
我能正确理解问题吗？你如何证明这个定理？
我建议你阅读这篇论文.这是一篇非常有趣和精彩的论文,可以在更低的时间范围内为您提供证据.(我认为你应该能够把它变成O(N ^ 2),或者你可以断定O(N*log(N))在技术上是O(N ^ 2)但直接遵循这个证明可能会让你的教授感到不安.我想他打算让你以不同的方式接近它.
编辑:
该论文的原始链接不再有效.这是另一个公开发布的.
http://www-dev.ccs.neu.edu/home/viola/classes/papers/PippengerF-Oblivious.pdf
"复杂性措施之间的关系",Michael J. Fischer和Nicholas Pippenger,1979年.