We investigate the relative computing power of Turing machines with differences in the number of work tapes, heads pro work tape, instruction repertoire etc. We concentrate on the k-tape, k-head and k-head jump models as well as the 2-way multihead finite automata with and without jumps. Differences in computing power between machines of unlike specifications emerge under the real-time restriction. In particular it is shown that k+1 heads are more powerful than k heads for real-time Turing machines.

Additional Metadata
Persistent URL dx.doi.org/10.1007/3-540-10003-2_106
Conference International Colloquium on Automata, Languages and Programming
Citation
Vitányi, P.M.B. (1980). On the power of real-time turing machines under varying specifications. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence (pp. 658–671). doi:10.1007/3-540-10003-2_106