On the simulation of many storage heads by one

AbstractEach multitape Turing machine, of which the storage heads scan O(log n) distinct squares in each interval of n steps, for all n ⩾ 1, can be real-time simulated by an oblivious `one-head tape unit. To simulate but the normal pushdown store, on-line by an oblivious one-head tape unit, requires ω(n√n) time. (This improves the known ω(n log n) lower bound for the on-line simulation of multitape Turing machines by oblivious one-tape Turing machines.