A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space (Q1199887): Difference between revisions

We consider the Turing machine model with a two-way, read-only input tape and a separate two-way, read-write worktape [\textit{J. E. Hopcroft} and \textit{J. D. Ullman}, Formal Languages and their relation to automata, Addison-Wesley (1969; Zbl 0196.017)]. Recently, \textit{D. Ranjan, R. Chang} and \textit{J. Hartmanis} [Theor. Comput. Sci. 80, 289-302 (1991; Zbl 0745.68051)] introduced a slightly modified Turing machine model, called a 1-inkdot Turing machine. The 1-inkdot Turing machine is a Turing machine with the additional power of marking one tape-cell on the input (with an inkdot). This tape-cell is marked once and for all (no erasing) and no more than one dot of ink is available. The action of the machine depends on the current state, the currently scanned input and worktape symbols and the presence of the inkdot on the currently scanned tape-cell. The action consists of moving the heads and making appropriate changes on worktape cells (using the finite control). In addition, the inkdot may be used to mark the currently scanned cell on the input tape if it has not been used already.