𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Relationships between nondeterministic and deterministic tape complexities

✍ Scribed by Walter J. Savitch

Publisher
Elsevier Science
Year
1970
Tongue
English
Weight
816 KB
Volume
4
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

The amount of storage needed to simulate a nondeterministic tape bounded Turing machine on a deterministic Turing machine is investigated. Results include the following: Theorem. A nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic [L(n)]2-tape bounded Turing machine, provided L(n) >~ log2 n. Computations of nondeterministic machines are shown to correspond to threadings of certain mazes. This correspondence is used to produce a specific set, namely the set of all codings of threadable mazes, such that, if there is any set which distinguishes nondeterministic tape complexity classes from deterministic tape complexity classes, then this is one such set.

πŸ“œ SIMILAR VOLUMES

Maze recognizing automata and nondetermi
Maze recognizing automata and nondeterministic tape complexity
✍ Walter J. Savitch πŸ“‚ Article πŸ“… 1973 πŸ› Elsevier Science 🌐 English βš– 682 KB

A new device called a maze recognizing automaton is introduced. The following two statements are shown to be equivalent. (i) There is a maze recognizing automaton that accepts precisely the threadable mazes. (ii) Every nondeterministic L(n)-tape bounded Turing machine can be simulated by a determini