On the power of real-time Turing machines under varying specifications; extended abstract : (preprint)
Paul M. B. Vitanyi · Data Archiving and Networked Services (DANS) · 1980
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+l heads are more powerful thank heads for real-time Turing machines.