Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings

Computational Complementarity for Mealy Automata

C. Calude
E. Calude
C. Stefanescu
Journal / Anthology

Bulletin of the European Association for Theoretical Computer Science
Year: 1998
Volume: 66
Page range: 139-150

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.

*Applied Mathematics > Computer Science