1983/11/01 by Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi +1 · 2 citations
Computer Science · #Computability, Logic, AI Algorithms #Cellular Automata and Applications #semigroups and automata theory
paper · doi:10.1109/sfcs.1983.39
openalex publication_date 1983/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.