A note on multi-inkdot nondeterministic Turing machines with small space (Q1334629)

The paper investigates the computational power of nondeterministic machines that are allowed to mark finitely many times the cells on the input tape. The main result states that for any \(k \leq 1\) there is a language \(L\) such that \(L\) is accepted by a nondeterministic Turing machine with \(k + 1\) inkdots that uses \(\log \log n\) space on any input of length \(n\), on all computations paths byt \(L\) is not accepted by any nondeterministic Turing machine with \(k\) inkdots that uses \(o(\log n)\) space on some accepting path for all accepted strings of length \(n\).