On the Power of Real-Time Turing Machines under Varying Specifications

摘要

The relative computing power of Turing machines with differences in the number of work tapes, heads per work tape and instruction repertoire is investigated. The k-tape, k-head and k-head jump models as well as the two way multihead finite automata with and without jumps are studied. 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.