Space bounds for processing contentless inputs

摘要

The space and time bounds of Turing machines which process contentless inputs, i.e., inputs of the form an are investigated. There is such a Turing machine which uses space bounded by log log n but not space bounded by any constant. Properties of this processor are given. The general properties of Turing machines processing contentless inputs are discussed. Any nontrivial processor can be transformed into a recognizer of a nonregular language in the same input alphabet and using exactly the same space. Finally, a theorem which establishes a hierarchy of contentless languages whose recognizers require at least log n space is given.