Information and the complementarity game

K. Svozil
Institut für Theoretische Physik
University of Technology Vienna
Wiedner Hauptstraß e 8-10/136
A-1040 Vienna, Austria
www:[  \tilde]svozil[  \tilde]svozil/publ/fis96.tex

Suppose the world is a machine. This is a long-held suspicion, at least as old as the Pythagoreans, that has been revitalized by the early natural sciences. Presently, this intuition is formalized by the computer sciences and constructive as well as discrete mathematics.

Of course, anybody claiming that the world is a machine is in a state of sin, in outright contradiction to the canon of physics, at least at the moment. We are told that certain quantum mechanical events occur randomly and uncontrollably; and chaos theory pretends us that there is randomness even in classical continuum mechanics and electricity.

In principle, the statement that the world is a machine is trivial; a self-fulfilling prophesy if you like. Because anything which we can be comprehended can automatically be called machine-like or constructive. Alternatively, if there would be no world comprehension, there would be no talk of the machine-like character of the world. But then there would most probably be no talk at all.

Having said this as a preamble, let me spell out one particular consequence of the assumption that the world is a machine a little bit more explicitly. There has been hardly any feature of quantum mechanics which has given rise to as many fruitless speculations as complementarity. Intuitively, complementarity states that it is impossible to (irreversibly) observe certain observables simultaneously with arbitrary accuracy. The more precisely one of these observables is measured, the less precisely can be the measurement of other-complementary-observables. Typical examples of complementary observables are position/momentum (velocity), angular momentum in the x/y/z direction, and particle number/phase [14,22].

The intuition (if intuition makes any sense in the quantum domain) behind this feature is that the act of (irreversible) observation of a physical system causes a loss of information by (irreversibly) interfering with the system. Thereby, the possibility to measure other aspects of the system is destroyed.

This appears to be not the whole story. Indeed, there is reason to believe that-at least up to a certain magnitude of complexity-any measurement can be ``undone'' by a proper reconstruction of the wave-function. A necessary condition for this to happen is that all information about the original measurement is lost. Schrödinger, the creator of wave mechanics, liked to think of the wave function as a sort of prediction catalog [20]. This prediction catalogue contains all potential information. Yet, it can be opened only at a single particular page. The prediction catalog may be closed before this page is read. Then it could be opened once more at another, complementary, page. By no way it is possible to open the prediction catalog at one page, read and (irreversibly) memorize (measure) the page, and close it; then open it at another, complementary, page. (Two non-complementary pages which correspond to two co-measurable observables can be read simultaneously.)

This may sound a little bit like voodoo. It is tempting to speculate that complementarity can never be modeled by classical metaphors. Yet, classical examples abound. A trivial one is a dark room with a ball moving in it. Suppose that we want to measure its position and its velocity. We first try to measure the ball's position by touching it. This finite contact inevitably causes a finite change of the ball's motion. Therefore, we cannot any longer measure the initial velocity of the ball with arbitrary position.

There are a number of more faithful classical metaphors for quantum complementarity. Take, for instance, Cohen's ``firefly-in-a-box'' model [3], Wright's urn model [24], as well as Aerts' vessel model [1]. In what follows, we are going to explore a model of complementarity pioneered by Moore [12]. It is based on extremely simple systems-probably the simplest systems you can think of-on finite automata. The finite automata we will consider here are objects which have a finite number of internal states and a finite number of input and output symbols. Their time evolution is mechanistic and can be written down on tables in matrix form. There are no build-in infinities anywhere; no infinite tape or memory, no non-recursive bounds on the runtime et cetera.

Let us develop computational complementarity, as it is often called [4], as a game between you as the reader and me as the author. The rules of the game are as follows. I first give you all you need to know about the intrinsic workings of the automaton. For example, I tell you, ``if the automaton is in state 1 and you input the symbol 2, then the automaton will make a transition into state 2 and output the symbol 0;'' and so on. Then I present you a black box which contains a realization of the automaton. The black box has a keyboard, with which you input the input symbols. It has an output display, on which the output symbols appear. No other interfaces are allowed. Suppose that I can choose in which initial state the automaton is at the beginning of the game. I do not tell you this state. Your goal is to find out by experiment which state I have chosen. You can simply guess or relying on your luck by throwing a dice. But you can also perform clever input-output experiments and analyze your data in order to find out. You win if you give the correct answer. I win if you guess incorrectly. (So, I have to be mean and select worst-case examples).

Suppose that you try very hard. Is cleverness sufficient? Will you always be able to uniquely determine the initial automaton state?

The answer to that question is ``no.'' The reason for this is that there may be situations when the input causes an irreversible transition into a state which does not allow any further queries about the initial state. This is the meaning of the term ``self-interference'' mentioned above. Any such irreversible loss of information about the initial value of the automaton can be traced back to many-to-one operations [8]: different states are mapped onto a single state with the same output. Many-to-one operations such as ``deletion of information'' are the only source of entropy increase in mechanistic systems [8,2].

In the automaton case discussed above, one could, of course, restore reversibility and recover the automaton's initial state by Landauer's ``Hänsel und Gretel''-strategy. That is, one could introduce an additional marker at every many-to-one node which indicates the previous state before the transition. Such a strategy would result in operations of information which are one-to-one (or one-to-many). But then, as the combined automaton/marker system is reversible, going back to the initial state erases all previous knowledge. This is analogous to the re-opening of pages of Schrödinger's prediction catalog.

In quantum mechanics, the time evolution of the system between two measurements can be represented by a unitary (i.e., invertible) transformation. Therefore, any information process is strictly one-to-one. (In general, one-to-many operations such as the copying of quantum information are forbidden [6,23,10,11,5].) The above mentioned ``Hänsel und Gretel''-strategy can in principle be adapted for the automaton model based complementarity game to accommodate such one-to-one operations.

Let us stop the general discussion at this point and introduce a sufficiently simple automaton example featuring computational complementarity. Consider an automaton which can be in one of three states, denoted by 1, 2 and 3. This automaton accepts three input symbols, namely 1, 2 and 3. It outputs only two symbols, namely 0 and 1. The transition function of the automaton is as follows: on input 1, it makes a transition to (or remains in) state 1; on input 2, it makes a transition to (or remains in) state 2; on input 3, it makes a transition to (or remains in) state 3. This is a typical irreversible many-to-one operation, since a particular input steers the automaton into that state, no matter in which one of the three possible state it was previously. The output function is also many-to-one and rather simple: whenever both state and input coincide-that is, whenever the guess was correct-it outputs 1; else it outputs 0. So, for example, if it was in state 2 or 3 and receives input 1, it outputs 0 and makes a transition to state 1. There it awaits another input. These automaton specifications can be conveniently represented by diagrams such as the one drawn in Fig. 1(a).

Picture Omitted


Picture Omitted

Figure 1: (a) transition diagram of a quantum-like finite automaton featuring computational complementarity. Input and output symbols are separated by a comma. Arrows indicate transitions. (b) Hasse diagram of its propositional structure. Lower elements imply higher ones if they are connected by edge(s).

Computational complementarity manifests itself in the following way: if one does not know the automaton's initial state, one has to make choices between the input of symbols 1, 2, or 3; corresponding to definite answers whether the automaton was in state 1, 2 or 3; in which case one would obtain the output 1; and (2 or 3), (1 or 3) or (2 or 3), in which case one would obtain output 0, respectively. In the latter case, i.e., whenever the automaton responds with a 0 (for failure), one has lost information about the automaton's initial state, since it surely has made a transition into the state 1,2 or 3. The following propositions can be stated. On input 1, one obtains information that the automaton either was in state 1 (exclusive) or not in state 1, that is, in state 2 or 3. This is denoted by v(1) = { {1},{2,3}}. On input 2, we obtain information that the automaton either was in state 1 (exclusive) or in state 1 or 3, denoted by v(2) = { {2},{1,3}}. On input 3, we obtain information that the automaton either was in state 1 (exclusive) or in state 1 or 2, denoted by v(3) = { {3},{1,2}}. In that way, we naturally arrive at the notion of a partitioning of automaton states according to the information obtained from input/output experiments. Every element of the partition stands for the proposition that the automaton is in (one of) the state(s) contained in that partition.

From any partition we can construct the Boolean propositional calculus which is obtained if we identify its atoms with the elements of the partition. We then ``paste'' all Boolean propositional calculi (sometimes called subalgebras or blocks) together. This is a standard construction in the theory of orthomodular posets [7,16,15,13]. In the above example, we arrive at a form of non-Boolean lattice whose Hasse diagram MO3 is of the ``Chinese latern'' type drawn in Fig. 1(b).

Let us go still a little bit further and ask which automaton games of the above kind can people play. This requires the systematic investigation of all possible non-isomorphic automaton propositional structures, or, equivalently, partition logics [21,17,18,19]. In Fig. 2, the Hasse diagrams of all non-isomorphic four-state automaton propositional calculi are drawn.



Figure 2: Variations of the complementarity game up to four automaton states.

New automata can be composed from old ones by parallel and serial compositions. In Figures 3 and 4, the Hasse diagrams for simple parallel compositions of two and three automata are drawn.

Picture Omitted

Figure 3: Hasse diagram of the automaton logic resulting from a parallel composition of two automata.

Picture Omitted

Figure 4: Hasse diagram of the automaton logic resulting from a parallel composition of three automata.

Recall that the method introduced here is not directly related to diagonalization and is a second, independent source of undecidability. It is already realizable at an elementary pre-diagonalization level, i.e., without the requirement of computational universality or its arithmetic equivalent. The corresponding machine model is the class of finite automata.

Since any finite state automaton can be simulated by a universal computer, complementarity is a feature of sufficiently complex deterministic universes as well. To put it pointedly: if the physical universe is conceived as the product of a universal computation, then complementarity is an inevitable and necessary feature of the perception of intrinsic observers. It cannot be avoided.

Conversely, any computation can be realized by a sufficiently complex finite automaton. Therefore, the class of all complementary games is a unique one, encompassing all possible deterministic universes.


Aerts, D. Example of a macroscopic classical situation that violates Bell inequalities. Lettere al Nuovo Cimento 34, 4 (1982), 107-111. The suggested analogy to two entangled spin-1/2 particles is challenged by the fact that the proposed expectation functions are not invariant with respect to temporal order.

Bennett, C. H. The thermodynamics of computation-a review. In International Journal of Theoretical Physics [9], pp. 905-940. Reprinted in [9].

Cohen, D. W. An Introduction to Hilbert Space and Quantum Logic. Springer, New York, 1989.

Finkelstein, D., and Finkelstein, S. R. Computational complementarity. International Journal of Theoretical Physics 22, 8 (1983), 753-779.

Glauber, R. J. Amplifyers, attenuators and the quantum theory of measurement. In Frontiers in Quantum Optics, E. R. Pikes and S. Sarkar, Eds. Adam Hilger, Bristol, 1986.

Herbert, N. FLASH-a superluminal communicator based upon a new kind of quantum measurement. Foundation of Physics 12, 12 (1982), 1171-1179.

Kalmbach, G. Orthomodular Lattices. Academic Press, New York, 1983.

Landauer, R. Information is physical. Physics Today 44 (May 1991), 23-29.

Leff, H. S., and Rex, A. F. Maxwell's Demon. Princeton University Press, Princeton, 1990.

Mandel, L. Is a photon amplifier always polarization dependent? Nature 304 (1983), 188.

Milonni, P. W., and Hardies, M. L. Photons cannot always be replicated. Physics Letters 92A, 7 (1982), 321-322.

Moore, E. F. Gedanken-experiments on sequential machines. In Automata Studies, C. E. S. anf J. McCarthy, Ed. Princeton University Press, Princeton, 1956.

Navara, M., and Rogalewicz, V. The pasting constructions for orthomodular posets. Mathematische Nachrichten 154 (1991), 157-168.

Peres, A. Quantum Theory: Concepts and Methods. Kluwer Academic Publishers, Dordrecht, 1993.

Piziak, R. Orthomodular lattices and quadratic spaces: a survey. Rocky Mountain Journal of Mathematics 21 (1991), 951.

Pták, P., and Pulmannová, S. Orthomodular Structures as Quantum Logics. Kluwer Academic Publishers, Dordrecht, 1991.

Schaller, M., and Svozil, K. Partition logics of automata. Il Nuovo Cimento 109B (1994), 167-176.

Schaller, M., and Svozil, K. Automaton partition logic versus quantum logic. International Journal of Theoretical Physics 34, 8 (August 1995), 1741-1750.

Schaller, M., and Svozil, K. Automaton logic. International Journal of Theoretical Physics 35, 5 (May 1996), 911-940.

Schrödinger, E. Die gegenwärtige Situation in der Quantenmechanik. Naturwissenschaften 23 (1935), 807-812, 823-828, 844-849. English translation in [22].

Svozil, K. Randomness & Undecidability in Physics. World Scientific, Singapore, 1993.

Wheeler, J. A., and Zurek, W. H. Quantum Theory and Measurement. Princeton University Press, Princeton, 1983.

Wooters, W. K., and Zurek, W. H. A single quantum cannot be cloned. Nature 299 (1982), 802-803.

Wright, R. Generalized urn models. Foundations of Physics 20 (1990), 881-903.

File translated from TEX by TTH, version 2.69.
On 5 Oct 2001, 12:04.