One-Tape, Off-Line Turing Machine Computations
One-Tape, Off-Line Turing Machine Computations
复制标题
DOI：
10.1016/s0019-9958(65)90399-2
复制
发表时间：
1965-12
期刊：
影响因子：
--
通讯作者：
F. Hennie
中科院分区：
文献类型：
--
作者：
F. Hennie
本文有两个目的。第一个是研究一类受限图灵机的特性，并开发一个简单的工具来描述它们的计算。第二个是提出具体的问题，可以找到严格的下限的计算时间所需的图灵机这一限制类。
This paper has two purposes. The first is to investigate the characteristics of a restricted class of Turing machines, and to develop a simple tool for describing their computations. The second is to present specific problems for which tight lower bounds can be found for the computation times required by Turing machines of this restricted class.