  We realize constant-space quantum computation by measure-many two-way quantum
finite automata and evaluate their language recognition power by analyzing
patterns of their exotic behaviors and by exploring their structural
properties. In particular, we show that, when the automata halt "in finite
steps" along all computation paths, they must terminate in worst-case liner
time. In the bounded-error probability case, the acceptance of the automata
depends only on the computation paths that terminate within exponentially many
steps even if not all computation paths may terminate. We also present a
classical simulation of those automata on two-way multi-head probabilistic
finite automata with cut points. Moreover, we discuss how the recognition power
of the automata varies as the automata's acceptance criteria change to error
free, one-sided error, bounded error, and unbounded error by comparing the
complexity of their computational powers. We further note that, with the use of
arbitrary complex transition amplitudes, two-way unbounded-error quantum finite
automata and two-way bounded-error 2-head quantum finite automata can recognize
certain non-recursive languages, whereas two-way error-free quantum finite
automata recognize only recursive languages.
