Deterministic one-way Turing machines with sublinear space

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

One can measure the complexity of systems by their space requirements as opposed to time. A strongly space-bounded Turing machine uses at most \(f(n)\) cells of the work tape on every input of length \(n\), \(f(n)\) is just a function. For logarithmic space bound, one-way machines retain only little information about the input on the work tape and only regular languages are accepted.NEWLINENEWLINEA weak space bound means that the Turing machine uses at most \(f(n)\) cells of the work tape on every accepted input of length \(n\), for rejecting the input no space bound is present. Restricted space bound is motivated by the study of \(P\) automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The Turing machine uses at most \(f(i)\) cells of the work tape in any configuration with input head at position \(i\), occurring in any accepting computation. It is demonstrated that every function \(f\) that is space-constructible by a deterministic two-way Turing machine, is space-constructible by a strongly \(f\) space-bounded deterministic one-way Turing machine. One-way Turing machines, contrary to two-way Turing machines, are not allowed to move the input head to the left.NEWLINENEWLINEFinally, closure properties under Boolean operations are obtained for weak space bounds.

Recommendations

Cited in

(7)

This page was built for publication: Deterministic one-way Turing machines with sublinear space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805402)