|
|
|
|
|
|
|
|
Computational Complementarity for Mealy Automata
|
|
|
|
|
|
|
|
|
|
|
|
Bulletin of the European Association for Theoretical Computer Science |
|
|
|
|
|
|
In this paper we extend (and study) two computational complementarity principles from Moore to Mealy automata which are finite machines processing better "quantum-like" features. We conjecture that automata which are reversible according to Svozil do not satisfy any of these computational complementarity principles. This result is consistent with the embeddability of irreversible computations into reversible ones (via Bennett's method, for example). Mathematica experiments confirmed this hypothesis.
|
|
|
|
|
|
|
|