Halting space-bounded computations
Halting space-bounded computations
复制标题
停止空间有限的计算
DOI：
10.1016/0304-3975(80)90053-5
复制
发表时间：
1978
期刊：
影响因子：
--
通讯作者：
M. Sipser
中科院分区：
文献类型：
--
作者：
M. Sipser
本文的主要结果是，对于任何确定性图灵机w！;，它在空间S（n）中运行，并且可能通过循环拒绝，存在一个等价的图灵机，它在相同的空间量中运行，并且从不循环。Hopcroft和Ullman [2]以前曾对S（n）2 lop yz证明了这一点，但猜想对小S这一点是错误的。他们对S（n）2 log yt的证明计算了磁带上一个单独轨道上的步骤，如果它有rtln太长时间，就关闭机器。Hartmanis和Berman [1]在一元语言上用更复杂的计数技术证明了S（n）< log n.除了空间有界的图灵机，我们的技术还适用于其他确定性计算模型.利用它，我们可以强制终止的双向有限自动机的状态数不呈指数增长，并在双向多头有限自动机不增加头的数量。然而，关于非确定性计算的类似问题仍然没有解决。
The main result of this paper is that for any deterministic Turing machine w!;, ich runs in space S (n) and which possibly rejects by looping, there is an equivaient Turing machine which runs in the same amount of space and never loops. Hopcroft and Ullman [2] have previously shown this for S (n) 2 lop yz but conjecture that it is false for small S. Their proof for S (n) 2 log yt counts steps on a separate track of the tape and shuts the machine off if it has rtln for too long. Hartmanis and Berman [I] prove this for S (n)< log n on unary languages with a more complicated counting technique.In addition to space bounded Turing machines, our technique applies to other deterministic computation models. Using it, we can enforce termination on twc-way finite automata without exponentially increasing the number of states and on two-way multihead finite automata without increasing the number of heads. The analogous questions about non-deterministic computation, however, remain open.