An improved simulation result for ink-bounded turing machines

摘要

A (one tape, deterministic) Turing Machine is f(n) ink bounded if the machine changes a symbol of its work tape at most f(n) times while processing an input of length n. The result of our paper is the construction of an “ink efficient” universal machine which, for any f(n) ink bounded machine M and input x, can simulate the processing of M on x or detect that M is looping infinitely on input x. The universal machine requires O(f(n)1+ϵ ink for this simulation, where e is an arbitrarily small positive number. As a corollary we establish that for ink-constructable g: For any ϵ > 0, if infn→∞(f(n)1+ge/g(n)) = 0 then there is a language in INK(g(n)) not in INK(f(n)).