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.

doi.org/10.1007/3-540-10003-2_106
European Conference on Numerical Mathematics and Advanced Applications
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Vitányi, P. (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