Title :
On determinism versus non-determinism and related problems
Author :
Paul, Wolfgang J. ; Pippenger, Nicholas ; Szemerédi, Endre ; Trotter, William T.
Abstract :
We show that, for multi-tape Turing machines, non-deterministic linear time is more powerful than deterministic linear time. We also discuss the prospects for extending this result to more general Turing machines.
Keywords :
Computational modeling; Laboratories; Legged locomotion; Time factors; Turing machines;
Conference_Titel :
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location :
Tucson, AZ, USA
Print_ISBN :
0-8186-0508-1
DOI :
10.1109/SFCS.1983.39
