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

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