Two tapes are better than one for off-line Turing machines | Zendy

Wolfgang Maass | Zendy; Georg Schnitger | Zendy; Endre Szemerédi | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Two tapes are better than one for off-line Turing machines

Author(s) -

Wolfgang Maass,

Georg Schnitger,

Endre Szemerédi

Publication year - 1987

Publication title -

citeseer x (the pennsylvania state university)

Language(s) - English

Resource type - Conference proceedings

ISBN - 0-89791-221-7

DOI - 10.1145/28395.28406

Subject(s) - turing machine , non deterministic turing machine , computer science , turing machine examples , super recursive algorithm , nondeterministic algorithm , turing , nspace , probabilistic turing machine , line (geometry) , universal turing machine , dtime , algorithm , mathematics , programming language , computation , geometry

We prove the first superlinear lower bound for a concrete decision problem in P on a Turing machine with one work tape and a two-way input tape (also called: off-line 1-tape Turing machine). In particular we show for off-line Turing machines that 2 tapes are better than 1 and that 3 pushdown stores are better than 2 (both in the deterministic and in the nondeterministic case).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research