Two-way finite automata with advice

Advice is trusted external assistance provided to a model of computation in the form of strings. Automata with advice has been studied since the work of Damm and Holzer. Recently Küçük et al. defined a model of advised automata where the advice string is put in a separate tape with its own dedicated head instead of appended in the beginning of input which had been the usual convention before. In this work we will adopt the model defined by Küçük et al. and introduce multiple input heads into it, which has not been done before. We show that it is possible to trade input heads with advice heads and vice versa when all heads are two-way and advice length is bounded by a polynomial function of input length and input length is bounded by a polynomial function of advice length. Frei et al. claimed that for short advices (whose logarithm grows slower than logarithm of logarithm of input length) neither non-determinism, nor two-way move- ment capability of input head, nor arbitrary number of additional advice heads (nor any combination of these) can help to deterministic automata with one one-way input head and one two-way advice head. We disprove this claim, and point to the error in the proposed proof. Specifically, we prove that as long as advice is more than constant, even the set of non-deterministic automata with one one-way input head and one one- way advice head recognize languages that are not recognizable by any deterministic automata with one one-way input head and any number of two-way advice heads. Frei et al. also claimed an improvement over the characterization of the problem class L/poly with automata that take advice by Holzer. We identify a mistake in the proposed proof of a lemma on which their result depends.