Maze recognizing automata and nondeterministic tape complexity

摘要

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 deterministic L(n)-tape bounded Turing machine, provided L(n)≥log2n.