On the structure of one-tape nondeterministic turing machine time hierarchy
On the structure of one-tape nondeterministic turing machine time hierarchy
复制标题
一盘非确定性图灵机时间层次结构的研究
DOI：
10.1016/0304-3975(85)90165-3
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
Kojiro Kobayashi
中科院分区：
文献类型：
--
作者：
Kojiro Kobayashi
我们证明，如果可用状态的数量是固定的并且足够大，那么单带非确定性图灵机在时间范围 a 2 f (n) 内可以接受比在 a 1 f (n) 内更多的集合，对于 0< a 1< a 2。这里，f (n) 是 n b 0 (log n) b 1 (log 2 n) b 2…(log h n) b h (b 0,…, b h 是有理数形式的任何函数。数），阶数为 n log n 和 n 2。使用交叉序列和 Kolmogorov 复杂度来证明这一点。
We show that if the number of available states is fixed and is sufficiently large, then one-tape nondeterministic Turing machines can accept more sets within time bound a 2 ƒ (n) than within a 1 ƒ (n), for 0< a 1< a 2. Here, ƒ (n) is any function of the form n b 0 (log n) b 1 (log 2 n) b 2…(log h n) b h (b 0,…, b h are rational numbers) with order n log n and n 2. Crossing sequences and Kolmogorov complexity are used to prove it.