A uniform approach to test computational complementarity
Elena Calude, Bruce Mills, Lan Mills · 2004
Information about the initial state of a nite automaton may be obtained by interacting with it. Some automata display behaviour analogous to quantum complementarity: two pieces of information can be obtained separately, but not in conjunction. Studies of two computational complementarity properties in nite state interactive automata may shed light on the nature of both quantum and classical computation. But, it can be dicult to determine the statistics of its occurrence. This paper introduces the concept of an observation graph of an automaton. The observation graph can be used as the foundation of algorithms for testing in a uniform manner for a variety of complementarity properties. Implementations have been run in practical time on a standard desktop computer examining all 6-state, 2-symbol automata.