A Space Bound for One-tape Multidimensional Turing Machines
Let L be a language recognized by a nondeterministic Turing machine with one d-dimensional worktape of time complexity T(n). Then L can be recognized by a deterministic Turing machine of space complexity (T(n)logT(n))^d/d+1. The prood employs a generalized crossing sequence argument.
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148972 |