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).
1mm
Picture Omitted
Picture Omitted
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.
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.
0.80mm
Picture Omitted
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.