𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Two tapes versus one for off-line Turing machines

✍ Scribed by Wolfgang Maass; Georg Schnitger; Endre Szemerédi; György Turán

Publisher
Springer
Year
1993
Tongue
English
Weight
603 KB
Volume
3
Category
Article
ISSN
1016-3328

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The reduction of tape reversals for off-
The reduction of tape reversals for off-line one-tape Turing machines
✍ Patrick C. Fischer 📂 Article 📅 1968 🏛 Elsevier Science 🌐 English ⚖ 554 KB

For off-line one-tape Turing machines the number of tape reversals required for various computations may be uniformly reduced by an arbitrary constant factor. ## Introduction In the studies of specific measures of computational complexity it has always been of interest to determine the "speed-up"

Guess-and-verify versus unrestricted non
Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines
✍ Martin Sauerhoff 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 258 KB

It is well known that a nondeterministic Turing machine can be simulated in polynomial time by a so-called guess-and-verify machine. It is an open question whether an analogous simulation exists in the context of space-bounded computation. In this paper, a negative answer to this question is given f