离线图灵机与单带图灵机的计算效率分析

An Analysis of the Difference in Computing Efficiency between Off-Line Turing Machine and Single-Tape Turing Machine

研究离线图灵机与单带图灵机的计算效率的差别，证明了一个在离线图灵机上计算时间复杂度为Ｏ（ｎ）的判断问题，在单带图灵机上的计算时间复杂度为Ｏ（ｎ￣２），从而证明这两类计算模型在计算速度上存在非线性差别。

he difference in the computing time between the off-line Turing machine and single-tape Turing machine is investigated.It is proved that a judgement with a computing timecomplexity of O(n)on an off-line Turing machine will need one of O(n2)if it is computed onasingle-tape Turing machine.It is clear that there exists a difference in the computing speedbetween thetwo machines.