1980-07-14
On the power of real-time turing machines under varying specifications
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| doi.org/10.1007/3-540-10003-2_106 | |
| European Conference on Numerical Mathematics and Advanced Applications | |
| Organisation | 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 |
|
