  We introduce a new type of nonuniform two--way automaton that can use a
different transition function for each tape square. We also enhance this model
by allowing to shuffle the given input at the beginning of the computation.
Then we present some hierarchy and incomparability results on the number of
states for the types of deterministic, nondeterministic, and bounded-error
probabilistic models. For this purpose, we provide some lower bounds for all
three models based on the numbers of subfunctions and we define two witness
functions.

Formal Languages and Automata Theory;Computational Complexity