On the power of real-time turing machines under varying specifications
Presented at the European Conference on Numerical Mathematics and Advanced Applications (July 1980), Noordwijkerhout, The Netherlands
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.
|European Conference on Numerical Mathematics and Advanced Applications|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
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