Wolfram Library Archive


Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title

Computational Complementarity for Mealy Automata
Authors

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
Description

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.
Subject

*Applied Mathematics > Computer Science