Complexity problems in real time computation
Walter A. Burkhard · 1970
The study of computational complexity is continued under the additional requirement that the Turing machines operate in real time. The work reported here is motivated by that of Rabin [R] which asks implicitly about the computational power of n tape vs n+1 tape real time Turing machines and that of Hartmanis [H] who attempts a complexity measure for Turing machines in terms of reversals.