Theory of one-tape linear-time Turing machines
Theory of one-tape linear-time Turing machines
复制标题
DOI：
10.1016/j.tcs.2009.08.031
复制
发表时间：
2003-10
期刊：
影响因子：
--
通讯作者：
K. Tadaki;T. Yamakami;Jack C. H. Lin
中科院分区：
文献类型：
--
作者：
K. Tadaki;T. Yamakami;Jack C. H. Lin
单带双向单头离线线性时间图灵机理论与多项式时间图灵机理论有本质的不同，因为这些机器与有限状态自动机密切相关。本文讨论了各种类型的单带图灵机的结构复杂性问题（确定性，非确定性，可逆，交替，概率，计数和量子图灵机），在线性时间停止，其中机器的运行时间被定义为任何最长计算路径的长度。我们探讨了单带线性-时间图灵机和澄清如何机器的资源影响其计算模式和权力。
A theory of one-tape two-way one-head off-line linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing machines and clarify how the machines’ resources affect their computational patterns and power.