Remarks on languages acceptable in log log n space (Q1107318)

A language is acceptable in the strong sense by a two-way nondeterministic Turing machine when all computation paths on every input stop and satisfy the space bound. The following main theorem is established. There exists a language which is acceptable in the strong sense by a two-way nondeterministic Turing machine in log log n space such that: if the language is not decidable by any two-way deterministic Turing machine in log log n space, then \(L\neq NL\).