Deterministic simulation of non-deterministic turing machines (Detailed Abstract)
Walter J. Savitch · 1969
Computations of non-deterministic Turing machines are shown to correspond to “solving” certain mazes. The storage needed to “solve” mazes is related to the storage needed to deterministically simulate non-deterministic Turing machines. In particular, it is shown that a non-deterministic L(n)-tape bounded Turing machine can be simulated by an (L(n))2-tape bounded Turing machine, provided L(n)≥log2n.