Uniform simulations of nondeterministic real time multitape Turing machines

From MaRDI portal





A new uniform technique is developed for the simulation of nondeterministic multitape Turing machines by simpler machines. For many types of restricted nondeterministic Turing machines it can now be proved that both linear time is no more powerful than real time, and multitape machines are no more powerful than machines with two tapes, one of which is a simple and normalized comparison type. This is an improvement over all previously known simulations in terms of weaker machines. As an application we obtain that, for all such machines, the class of languages accepted in real time by multitape machines is principal and has a simple trio generator. Moreover, multitape machines with different types of tapes are hierarchically related, contrasting with the case of one-tape machines, and some important families of languages are characterized in a new way.











This page was built for publication: Uniform simulations of nondeterministic real time multitape Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3771615)