Physical versus Computational Complementarity I¹

Cristian Calude,²     Elena Calude,³     Karl Svozil,⁴     Sheng Yu⁵

Abstract

The general conception dominating the sciences is that the physical universe is perceivable only from inside. This view reduces the exophysical perception to a theoretical illusion. The more plausible perception, i.e. an endophysical one, suffers from a ``self-referential" disease as any intrinsic measurement causes uncontrolled, and maybe uncontrollable, ``disturbances" to the entity intended to be measured.

This paper, the first in a proposed series, discusses some limitations and trade-offs between endophysical/intrinsic and exophysical/extrinsic perceptions, in both physical and computational contexts. We are building our work on Moore ``Gedanken" experiments [] in which the universe is modeled by a finite deterministic automaton. A new type of computational complementarity, which mimics the state of quantum entanglement, is introduced and contrasted with Moore's computational complementarity. Computer simulations of both types of computational complementarity are developed for four-states Moore automata.

1  Introduction

1.1  Physical Complementarity

Physical complementarity appears to be a rather straightforward consequence of the quantum formalism. Yet, the conceptualization of complementarity has caused considerable attention, concern, thought and neglect [,]. Indeed, physical complementarity is tied up with measurement. The notion of measurement, in turn, is a highly nontrivial matter, as contemplations by Wigner [], Wheeler [], and Bell [], among many others, show.

How subtle the issue may get can be best demonstrated by the fact that in certain instances it is possible to ``reconstruct'' the quantum wave function after its alledged ``collapse'' []. Thereby, not a single (quantum) bit of information should remain available from the previous ``measurement''. In such a scenario, it is possible to ``measure'' complementary observables: the price to be paid amounts to the total ignorance of the first ``measurement outcome''.

Recently, schemes for an ``interaction-free wave function collapse'' associated with ``interaction-free'' measurement schemes have got renewed attention [,,,]. Compare Bohr's statement (cf. [], reprinted in [])

¼ the quantum postulate implies that any observation of atomic phenomena will involve an interaction with the agency of observation not to be neglected. ¼ the impossibility of neglecting the interaction with the agency of measurement means that every observation introduces a new uncontrollable element. Indeed, it follows ¼ that the measurement of the positional co-ordinates of a particle is accompanied not only by a finite change in the dynamical variables, but also the fixation of its position means a complete rupture in the causal description of its dynamical behaviour, while the determination of its momentum always implies a gap in the knowledge of its spatial propagation.

No observation can be made with less than one quantum passing through the observed object.

What is measurement? If it is simply information transfer, that is done all the time inside the computer, and can be done with arbitrarily little dissipation.

if the applicability [[operationalizability]] of the one (e.g., position coordinate) stands in the relation of exclusion to that [[operationalizability]] of the other (e.g., momentum)

The ``canonical'' understanding of complementarity is expressed in Messiah []

The description of properties of microscopic objects in classical terms requires pairs of complementary variables; the accuracy in one member of the pair cannot be improved without a corresponding loss in the accuracy of the other member.

           

It is impossible to perform measurements of position x and momentum p with uncertainties (defined by the root-mean square deviations) Dx and Dp such that the product of Dx Dp is smaller than a constant unit of action [((^h/_2p))/ 2].

In Prigogine's words [],

the world is richer than it is possible to express in any single language.

1.2  Moore ``Gedanken" Experiments

In the next section we shall present the formal notion of a finite automaton. To understand Moore's approach it is enough, at this stage, to say that the machines we are going to consider are finite in the sense that they have a finite number of states, a finite number of input symbols, and a finite number of output symbols. Such a machine has a strictly deterministic behaviour: the current state of the machine depends only on its previous state and previous input; the current output depends only on the present state.

A (simple) Moore experiment can be described as follows: a copy of the machine will be experimentally observed, i.e. the experimenter will input a finite sequence of input symbols to the machine and will observe the sequence of output symbols. The correspondence between input and output symbols depends on the particular chosen machine and on its initial state. The experimenter will study the sequences of input and output symbols and will try to conclude that ``the machine being experimented on was in state q at the beginning of the experiment".⁶

Moore's experiments have been studied from a mathematical point of view by various researchers, notably by Ginsburg [], Gill [], Chaitin [], Conway [], and Brauer [].

1.3  Finite Deterministic Automata

A finite deterministic automaton consists of a finite set of states and a set of transitions from state to state that occur on input symbols chosen from some fixed alphabet. For each symbol there is exactly one transition out of each state, possible back to the state itself. So, formally, a finite automaton consists of a finite set Q of states, an input alphabet S, and a transition function d: Q ×S® Q. Sometimes a fixed state, say 1, is considered to be the initial state, and a subset F of Q denotes the final states.

A Moore automaton is a finite deterministic automaton having an output function f: Q ® O, where O is a finite set of output symbols. At each time the automaton is in a given state q and is continuously emitting the output f(q). The automaton remains in state q until it receives an input signal s, when it assumes the state d(q, s) and starts emitting f(d(q, s)).

In this paper we are going to almost exclusively concentrate on the case of automata on a binary alphabet

S = {0,1} having O = S. So, from now on, a Moore automaton will be just a triple M = (Q, d, f).

Let S^* be the set of all finite sequences (words) over the alphabet S, including the empty word e; by S⁺ we denote S^* \{e}. The transition function d can be extended to a function [`(d)] : Q ×S^* ® Q, as follows:

The output produced by an experiment started in state q with input sequence w Î S^* is described by E(q,w), where E is the function

Consider, for example, Moore's automaton, in which Q = {1, 2, 3, 4},

S = {0,1}. The transition is given by the following tables

and the output function is defined by f(1) = f(2) = f(3) = 0, f(4) = 1.

The following graphical representation will be consistently used in what follows:

The experiment starting in state 1 with input sequence 000100010 leads to the output 0100010001. Indeed,

Let M = (Q, d, f) be a Moore automaton. The language generated by M on the state q is L(M, q) = {w Î S^* \mid f([`(d)](q,w)) = 1}. It is algorithmically decidable whether two languages L(M, q), L(M¢, q¢) are equal or not, Hopcroft and Ullman [].

1.4  Reversibility

A new perspective on this issue came recently from computation theory.¹⁰ Today's computers erase a bit of information every time they perform a computation corresponding to a many-to-one operation, cf. Landauer [], Bennett [,], Fredkin and Toffoli []. Therefore, computational operations, such as the explicit deletion of information or clearing some memory and that like, are ``irreversible." In spite of the fact that in the last 50 years the dissipated energy per bit of computational operation has decreased by roughly tenfold each five years, cf. Landauer [], the erasure is done very inefficiently, and much more than kT energy is dissipated for each bit erased.¹¹

In order to improve the computer hardware performance we have to continue to reduce the energy dissipated by each computational operation. There are two alternative ways to approach this problem: a) improving by conventional methods, i.e. improving the efficiency with which we erase information; b) ultimately use computational operations that do not erase information, i.e. the so-called ``reversible" computational operations, which can, in principle, dissipate arbitrarily little heat.¹²

The above facts show clearly how important is to model the idea of reversible computational operation (for an excellent discussion see the paper by Bennett and Landauer []). In our case, of finite automata, a possible definition is the following: the automaton (Q, d, f) is reversible if for every states p, q Î Q and u Î S^* with [`(d)](p,u) = q, there exists a word w Î S<sup>*</sup> such that [`(d)](q,w) = p. In other words, every input state of a computation can be ``reached back" from the final state of the computation, by means of a suitable computation. A stronger definition was studied in the literature (see Bavel and Muller []); we will return to it later.

2  Moore's Uncertainty Revisited

2.1  Indistinguishability

An equivalent way to express the indistinguishability of the states q and q¢ is to require, following Conway [], that for all w Î S^*,

A pair of states will be said to be ``distinguishable" if they are not ``indistinguishable", i.e. if there exists a string x Î S⁺, such that E(q , x) ¹ E(q¢, x).

Moore [] has proven the following important theorem: There exists a Moore automaton M such that any pair of its distinct states are distinguishable, but there is no experiment which can determine what state the machine was in at the beginning of the experiment. He is using the automaton displayed in Figure 1 and the argument is simple. Indeed, each pair of distinct states can be distinguished by an experiment: 1, 2 by x = 0, 1, 3 by x = 1, 1, 4 by x = 0, 2, 3 by x = 0, 2, 4 by x = 0, and 3, 4 by x = 0.

However, there is no (unique) experiment capable to distinguish between every pair of arbitrary distinct states. Two cases have to be examined:

A) The experiment starts with 1, i.e. x = 1u, u Î S^*. In this case E(1, x) = E(2, x), that is x cannot distinguish between the states 1, 2 as

B) The experiment starts with 0, i.e. x = 0v, v Î S^*. In this case

2.2  Computational Complementarity

Moore's theorem, described in the above section, can be thought of as being a discrete analogue of the Heisenberg uncertainty principle. The state of an electron E is considered specified if both its velocity and its position are known. Experiments can be performed with the aim of answering either of the following:¹⁴

1. What was the position of E at the beginning of the experiment?

2. What was the velocity of E at the beginning of the experiment?

For a Moore automaton, experiments can be performed with the aim of answering either of the following:

1. Was the automaton in state 1 at the beginning of the experiment?

2. Was the automaton in state 2 at the beginning of the experiment?

In either case, performing the experiment to answer question 1 changes the state of the system, so that the answer to question 2 cannot be obtained. This means that it is only possible to gain partial information about the previous history of the system, since performing experiments causes the system to ``forget" about its past.

Moore's automaton is a simple model featuring an ``uncertainty principle'' (cf. Conway []), later termed ``computational complementarity'' by Finkelstein and Finkelstein []. These type of models have been intensively studied from the point of view of their experimental logical structure by Grib and Zapatrin [,], as well as by Svozil [], Schaller and Svozil [,,] and Dvureenskij, Pulmannová and Svozil []. See Svozil and Zapatrin [] for a comparison of models.¹⁵

In what follows we are going to introduce two non-equivalent concepts of computational complementarity based upon modeling finite automata. Informally, they can be expressed as follows. Consider the class of all elements of reality¹⁶ and consider the following properties.

• Any two distinct elements of reality can be mutually distinguished by a suitably chosen measurement procedure [].

• For any element of reality, there exists a measurement which distinguishes between this element and all the others. That is, a distinction between any one of them and all the others is operational.

• There exists a measurement which distinguishes between any two elements of reality. That is, a single pre-defined experiment operationally exists to distinguish between an arbitrary pair of elements of reality. (Classical case.)

A natural questions arises: Does there exist automata having property C? The answer is affirmative and here is an example of such automaton:¹⁷

The experiment 10 distinguishes between any pair of distinct states. An automaton having C but requiring a longer experiment is presented in Section 2.4.

Complementarity corresponds to the following cases:

• Property A but not property B (and therefore not C): The elements of reality can be mutually distinguished by experiments, but one of these elements cannot be distinguished from all the other ones by any single experiment.

• Property B but not property C: Any element of reality can be distinguished from all the other ones by a single experiment, but there does not exist a single experiment which distinguishes between any pair of distinct elements.

Only the second type of complementarity deserves more attention. A Moore automaton has CII in case:

1. for every state q there exists an experiment w_q (depending upon q) such that E(q, w_q ) ¹ E(q¢, w_q ), for every state q¢ different from q, and
2. for every experiment w there exists at least two distinct states q,q¢ (depending upon w) such that E(q, w) = E(q¢, w).

In view of 2), each experiment ``generates" a pair of distinct states which exercise a mutual influence, namely they cannot be separated by the experiment w; this influence mimics, in a sense, the state of quantum entanglement.<sup>18</sup> To put it very pointedly, CII may be conceived as a toy model for the EPR effect (see [,,]), as well as for the Zou-Wang-Mandel effect [,,]. Under CII , for each experiment w we have at least two states q,q¢ (as distant as we like in terms of the emitting outputs f(q), f(q¢)) which interact via the experiment w: any measurement of q is affecting q¢ and, conversely, any measurement of q¢ is affecting q. It is interesting to note that this explanation supports Penrose view ([]) that EPR effects are puzzle mysteries, that is genuinely puzzling, but directly experimentally supported. Greenberger, Horne and Zeilinger call similar experiences simply mindboggling []. In fact, a second ``reading" of these phenomena could prove that their puzzling nature might ``not be so puzzling", after all. ¹⁹

>From a mathematical point of view properties A, B, C can be expressed as follows. Let M = (Q, d, f) be a Moore automaton.

• The automaton M has property A if every pair of different states of M are distinguishable, i.e. for every distinct states q, q¢ there exists a word w Î S⁺ (depending upon q,q¢) such that E(q,w) ¹ E(q¢,w).

• The automaton M has property B if every state of M is distinguishable from any other distinct state, i.e. for every state q there exists a word w Î S⁺ (depending upon q) such that E(q,w) ¹ E(q¢,w), for every state q¢ distinct from q.

• The automaton M has property C if there exists an experiment distinguishing between each different states of M, i.e. there exists a word w Î S⁺ such that E(q,w) ¹ E(q¢,w), for every distinct states q, q¢.

Indeed, the following pairs of states are distinguishable by every experiment: (1, 2), (1, 4), (2, 3), (3, 4). Accordingly, 1 is distinguishable from the other states by w = 0, 2 is distinguishable by w = 1, 3 is distinguishable by w = 0 and 4 is distinguishable by w = 1, so the automaton has property B. It does not have property C because:

• any experiment w which starts with 1, i.e. w = 1x,  x Î S^*, does not distinguish between 1 and 3;

• any experiment w which starts with 0, i.e. w = 0y,   y Î S^*, does not distinguish between 2 and 4.

The above example, though easy to deal with, is not very interesting²⁰ as the automaton is not reversible (we can reach 4 from 1, but we cannot get from 1 from 4).

Before studying further the above phenomena we will have to deal with some natural mathematical questions: a) is each of the properties A, B, C decidable?, b) how difficult is to test these properties?

2.3  Deciding Properties A, B, C

Are properties A, B, C algorithmically decidable? From the work of Conway [], it follows directly that the problem of testing whether two states are or not distinguishable is algorithmically decidable. This means that A is algorithmically decidable. In this section we will present a uniform proof for the decidability of properties A, B, C.²¹

Start with the automaton M = (Q, d, f) and for each state q Î Q construct the finite deterministic automaton

Accordingly, for p Î Q and (s₁, t₁)(s₂, t₂) ¼(s_n, t_n) Î (S²)^*,

We claim that for every states p,q Î Q,

Assume first that p and q are distinguishable, that is, there exists w Î S⁺ such that E(p,w) ¹ E(q,w). Let w = s₁ ¼s_n and E(p,w) = t₁t₂ ¼t_n+1. Take an arbitrary letter s_n+1 Î S and put

Conversely, assume that L(M_p) ¹ L(M_q). Then, there exists a Î L(M_p) \L(M_q) (or a Î L(M_q) \L(M_p)). Let

a = (s₁, t₁)(s₂, t₂) ¼(s_n, t_n), and w = s₁ s₂ ¼s_n-1. From hypothesis, E(p,w) = t₁ ¼t_n   (a Î L(M_p)), but E(q, w) ¹ t₁ ¼t_n   (a\not Î L(M_q)), so E(p, w) ¹ E(q, w), i.e. p,q are distinguishable.

We are now able to conclude that properties A, B, C are algorithmically decidable. Indeed, first we notice that

For B let M_q, q Î Q be defined as above. For each q Î Q define the set

As the problem of testing whether L(M_p) ¹ L(M_q) is algorithmically decidable, it follows that A is decidable.

Another way of computing the sets S(q) is to define:

Consequently, the set S(q) can be defined by

Clearly,

Finally, the decidability of C follows from the formula:

2.4  Complexity Issues

First we note that complementarity properties CI, CII cannot appear for Moore automata with less than four states.²² Indeed, if M = (Q, d, f) has less than two states the statement is clear. So, let Q = {1, 2, 3}. We only need to consider two cases:²³

1. if f(1) = f(2) = f(3), then no pair of states is distinguishable;

2. if f(1) = f(2) and f(1) ¹ f(3), and the states 1, 2 are distinguishable, then there exists an experiment w Î S⁺ such that E(1, w) ¹ E(2, w). Since f(1) = f(2) ¹ f(3), E(1, w) ¹ E(3, w) and E(2, w) ¹ E(3, w). Accordingly, A is equivalent to C.

An interesting problem is to evaluate how difficult it is to test properties A, B, C. A way to look at this problem is to evaluate the shortest length of experiments needed to decide properties A, B, C. This problem has been studied for A by some authors, for instance Chaitin [], Conway []. The main result (for a binary alphabet) can be stated as follows: to test A it is sufficient to test the condition E(q,w) ¹ E(q¢,w) for all words of length less than #(Q) -2. In fact, it is trivial to notice that we need only to test the above condition for words of length equal to #(Q)-2.

This result is no longer true for B and C. Indeed, 101010101 is the shortest word that distinguishes every pair of states in the automaton M = ({1, 2, 3, 4, 5, 6, 7}, d, f) displayed in Figure 4.²⁴

Here is the argument. Each w Î 1⁺01⁺01⁺01⁺01(0+1)^* can distinguish every pair of states in M. The shortest word in that set is w = 101010101. No shorter experiment can replace w:²⁵

• every word w Î 0(0+1)^* cannot distinguish between states 5, 6,

• every word w Î 1⁺00(0+1)^* cannot distinguish between states 4, 5,

• every word w Î 1⁺01⁺00(0+1)^* cannot distinguish between states 3, 4,

• every word w Î 1⁺01⁺01⁺00(0+1)^* cannot distinguish between states 2, 3,

• every word w Î 1⁺01⁺01⁺01⁺00(0+1)^* cannot distinguish between states 1, 2.

2.5  Operators

A probably better physical way to look at an automaton, which is equivalent to the classical mathematical one, is to think of M in terms of the transformations (operators) T_s: Q ®Q,   s Î S,  T_s(q) = d(q, s), as ``push buttons" allowing the automaton to change its states. Mathematically, we shall associate to M a class of operators (T_w)_{w Î S^*},

Sometimes the monoid of operators is a group, and in this special situation both types of complementarity disappear.²⁷ Here is the mathematical justification.

The following three statements are equivalent:

1. The operators (T_w)_{w Î S} form a group.
2. Each operator T_s,  s Î S is bijective.²⁸

3. Every operator T_s, s Î S has a right inverse.

The implications from G1) to G2) and from G2) to G3) are trivial. So, let us assume that G3) holds true, i.e. for every s Î S there exists a word x_s (depending upon s) such that T_sxs = T_e. We shall prove G1).

Note first that each operator has a right inverse, that is for each word u there corresponds a word [`u] such that T<sub>u[`u]</sub> = T_e. Indeed, if u = s₁ s₂¼s_n, then [`u] = x<sub>sn</sub> ¼x<sub>s1</sub> does the job. Now take p = T<sub>[`u]u</sub>(q). As

Using again the hypothesis and the above equality we get

Each of the above equivalent conditions G1) - G3) implies the equivalence of A, B and C. Indeed, every operator T_w has an inverse T<sub>[`w]</sub>. If M has A, then for each pair of distinct states q, q¢ there exists a word w<sub>q,q¢</sub> such that E(q, w<sub>q,q¢</sub>) ¹ E(q¢, w<sub>q,q¢</sub>). To get an experiment which globally distinguishes between any two distinct states we proceed as follows: we concatenate all words w<sub>q,q¢</sub>[`(w_q,q¢)] (when q, q¢ range in Q and are distinct) and we get the word w such that for all distinct states q,q¢ satisfies E(q, w) ¹ E(q¢, w).

Intuitively, the statement ``G1) - G3) implies the absence of complementarity" can be understood as follows. Suppose an automaton has one of the equivalent properties G1) - G3). Suppose further that an observer obtains a single copy of it and adopts the following strategy. The observer runs an arbitrary number of independent experiments. After each experiment, the observer records its outcome and steers the automaton back to its original (unknown) state.²⁹ In this way, the observer can make sure that the experiment does not irreversibly destroy potential information about the initial state of the automaton. Indeed, the setup is similar to Moore's multi-automaton configuration, with the only difference that not all experiments are performed simultaneously, but only one at a time. In that way, total and thus classical knowledge of the initial state is obtained.

This strategy fails for quantum systems. There, it is only possible to ``reverse the wave function collapse" (``reconstruct the state") if no knowledge of the measurement outcome is left over. All obtained information is needed in the reconstruction process itself. And, since any copying of proper q(u)bits of quantum information is not allowed, the strategy fails to produce the classical ``elements of reality." Because, stated pointedly, the observer either can make sure that he recovers the original system, (exclusive) or records a single measurement outcome associated with one particular experiment.

>From an observer ``from inside" the automaton is reversible, i.e. each computation can be reversed. To be more precise, an ``inside observer" can reverse any computation, but the proof that each computation can be reversed can be achieved only at the meta-level, i.e. at the level of a language ``speaking about the automaton". An external observer is ``losing" information in the process of monitoring only the outcomes: for such an observer some computations cannot be reversed.

2.6  Measuring the Complexity of Automata

The size of the monoid of operators is a measure of the complexity of the automaton. In what follows we shall refer to this measure as the ``size of the automaton".

Experimental tests for the case of four-states automata show that each automaton satisfying CI or CII has a non-commutative monoid of operators. In physical terms, non-commutativity is a mathematical form of complementarity, meaning that ``there is no state in which both measurables have well-defined values simultaneously".

How far could one go from the monoid structure associated with automata to the unitary transformations encountered in the evolution of quantum mechanical states between measurements? A few warnings should be issued at the very beginning. Automaton logic, like quantum logic, is static. It is not concerned with dynamical processes but with the inference of operational statements and their interrelation. Also, quantum systems are defined in the entire richness of finite/infinite dimensional Hilbert spaces and it can be expected that no finite structure can faithfully represent such wealth of mathematics []. Therefore, there is little hope for complete ``isomorphism".

But can one go further and find a correspondent for unitarity? That is, what corresponds to complex conjugation * and transposition t in the automaton context? As has been pointed out above, the composition (U^*)^t should correspond to the reverse transition U^-1 (which exists when the operators monoid is a group; in such a case the automaton is reversible). There is one more issue: Unitary transformations are generated by Hermitian ones via U(n) = exp[itH(n)]. Could the Hamiltonian H(n) be given any meaning in the automaton context? We shall leave these questions open at the moment.

2.7  Complementarity: Reversible Instances

Recall that the automaton (Q, d, f) was termed reversible³⁰ if for every states p, q Î Q and u Î S^* with [`(d)](p,u) = q, then there exists a word w Î S<sup>*</sup> such that [`(d)](q,w) = p.

The following two conditions are each equivalent to reversibility:

1. for all q Î Q and w Î S^* there exists a word u Î S^* such that [`(d)](q,wu) = q;

2. for every state q Î Q and s Î S there exists a word v_s^q Î S^* (depending upon s and q) such that [`(d)](q, sv_s^q) = q.

We have to prove only the equivalence between the last condition and reversibility. Indeed, if u = s₁ ¼s_n, then

Each of the above conditions is decidable, as we only need to examine only words of length less than the size of Q, due to the Pumping Lemma (see Hopcroft and Ullman []): for all q Î Q, u Î S^*,  [`(d)](q, u) = [`(d)](q, w), for some w Î S^* with length less than the size of Q.

Experimental computations³¹ show that out of 359,040³² reversible four-states automata:

• 26,688 satisfy CI; the minimal size of an automaton displaying CI is 8 (see an example in Figure 5); the maximal size is 79 (see an example in Figure 7);

• 16,128 satisfy CII; the minimal size of an automaton displaying CI is 9 (see an example in Figure 6); the maximal size is 145 (see an example in Figure 8).

We start with examples of automata having CI, CII and minimal size. The automaton in Figure 5 has CI:

Indeed, the automaton has A: the pairs of states (1, 2), (1, 3), (1, 4) are distinguishable by any experiment, (2, 3) and (2, 4) can be distinguished by w = 1, and (3, 4) can be distinguished by w = 01. The automaton has not B as for 4:

• every experiment w of the form 0y,   y Î S^* does not distinguish between 2 and 4, and
• every experiment w of the form 1y,   y Î S^* does not distinguish between 3 and 4.

The monoid of operators has 8 elements

and the induced table is the following:

The automaton in Figure 6 satisfies CII:

The automaton has B: the states (1, 2), (1, 4), (2, 3), (3, 4) are distinguishable by any experiment, so the state 1 can be distinguished from any other state by w = 1, 2 can be distinguished by w = 0, 3 can be distinguished by w = 1, and 4 can be distinguished by w = 0. It has not C as:

• if w = 0y,  y Î S^*, then 1 and 3 are not distinguishable,
• if w = 1y,  y Î S^*, then 2 and 4 are not distinguishable.

In this case the monoid of operators has 9 elements

and the induced table is the following:

We continue with examples of automata having CI, CII and maximal size. The automaton in Figure 7 has CI and maximum size (i.e 79):

The pair of states (1, 2), (1, 3), (1, 4) can be distinguished by any experiment. For (2, 3) and (2, 4) we can use w = 1; for (3, 4) we can use w = 0. So, it has A.

The automaton has not B as (2, 4) cannot be distinguished by any experiment w = 0y,  y Î S^* and (3, 4) cannot be distinguished by any experiment w = 1y,  y Î S^*.

The automaton in Figure 8 has CII maximum size (i.e 145):

The pair of states (1, 2), (2, 3), (2, 4) can be distinguished by any experiment. The state 1 can be distinguished by any other state by w = 1, 2 can be distinguished by any experiment, 3 can be distinguished by w = 001, and 4 can be distinguished by w = 01. So, it has B.

The automaton has not C as

• (3, 4) cannot be distinguished by any experiment w = 1y,  y Î S^*;

• if w = 0ⁿ, for some n ³ 1, then 1 and 3 cannot be distinguished: E(1, Oⁿ) = 0ⁿ⁺¹ = E(3, Oⁿ);

• if w = 0³ⁿ1y, for some y Î S^*, n ³ 1, then 3 and 4 cannot be distinguished: E(1, O³ⁿ1) = 0³ⁿ⁺² = E(4, O³ⁿ1) and [`(d)](3, 0<sup>3n</sup>1y) = [`(d)](3, 1y) = [`(d)](1,y) = [`(d)](4, 1y) = [`(d)](4, 0³ⁿ1y);

• if w = 0³ⁿ01y, for some y Î S^*, n ³ 1, then 1 and 3 cannot be distinguished: E(1, O³ⁿ01) = 0³ⁿ⁺³ = E(4, O³ⁿ01) and [`(d)](1, 0<sup>3n</sup>01y) = [`(d)](1, 01y) = [`(d)](1,y) = [`(d)](3, 01y) = [`(d)](3, 0³ⁿ01y);

• if w = 0³ⁿ001y, for some y Î S^*, n ³ 1, then 1 and 4 cannot be distinguished: E(1, O³ⁿ001) = 0³ⁿ⁺⁴ = E(1, O³ⁿ001) and [`(d)](1, 0<sup>3n</sup>001y) = [`(d)](1, 001y) = [`(d)](1,y) = [`(d)](4, 001y) = [`(d)](4, 0³ⁿ001y).

2.8  More About Moore's Example

Let us prove CII for the first choice of f. Moore's automaton has B as for 1 we can use w = 01, for 2 we can use w = 001, for 4 we can use w = 1 (any w is good for 3). The automaton has not C as:

• (1, 2) cannot be distinguished by any experiment w = 1y,  y Î S^*;

• if w = 0ⁿ, for some n ³ 1, then 1 and 2 cannot be distinguished: E(1, Oⁿ) = 0ⁿ⁺¹ = E(2, Oⁿ), [`(d)](1, 0) = 4,[`(d)](1,00) = 2,[`(d)](1,000) = 1,[`(d)](2, 0) = 1,[`(d)](2,00) = 4,[`(d)](2,000) = 2;

• if w = 0³ⁿ1y, for some y Î S^*, n ³ 1, then 1 and 2 cannot be distinguished: E(1, O³ⁿ1) = 0³ⁿ⁺² = E(2, O³ⁿ1) and [`(d)](1, 0<sup>3n</sup>1y) = [`(d)](3, 1y) = [`(d)](3,y) = [`(d)](2, 1y) = [`(d)](2, 0³ⁿ1y);

• if w = 0³ⁿ01y, for some y Î S^*, n ³ 1, then 2 and 4 cannot be distinguished: E(2, O³ⁿ01) = 0³ⁿ⁺³ = E(4, O³ⁿ01) and [`(d)](2, 0<sup>3n</sup>01y) = [`(d)](2, 01y) = [`(d)](3,y) = [`(d)](4, 01y) = [`(d)](4, 0³ⁿ01y);

• if w = 0³ⁿ001y, for some y Î S^*, n ³ 1, then 1 and 4 cannot be distinguished: E(1, O³ⁿ001) = 0³ⁿ⁺⁴ = E(1, O³ⁿ001) and [`(d)](1, 0<sup>3n</sup>001y) = [`(d)](1, 001y) = [`(d)](3,y) = [`(d)](4, 001y) = [`(d)](4, 0³ⁿ001y).

2.9  Complementarity: Non-Reversible Instances

In case of non-reversible automata the sizes of automata having CI or CII decrease, in the minimal cases, to 3. Here are two examples.

The automaton in Figure 10 has CI . Indeed, the automaton has A: the pairs (1, 2), (1, 3), (1, 4) are distinguishable by any experiment, the word w = 1 distinguishes between 2, 3, and 2, 4, while w = 0 distinguishes between 3 and 4. The automaton has not B as the state 3 cannot be distinguished from 2 by any experiment starting with 0, and 3 cannot be distinguished from 4 by any experiment starting with 1.

The operators induced by the automaton in Figure 10 and their composition table are presented below:

The automaton in Figure 3 has CII (see the proof in Section 2.2). This automaton has minimum size, i.e. 3, which makes the proof for non C quite easy. In this case we have three operators (T_e, T₀, T₁)-which are different from the operators of the automaton from Figure 7,

but their composition tables do coincide.

3  More About Actors and Spectators

In fact, we believe that a bit of the mystery associated with EPR effects, in general, and with CII , in particular, might not be so ``puzzling" at all, and here are two arguments.

A random (binary) sequence in Chaitin-Martin-Löf sense (see Chaitin [,], Calude []) is the prototype of the ideal chaotic sequence, in which no prediction is possible to come true and no computation can be successful in approximating more than a finite part of the sequence. However, such a sequence satisfies some very interesting, deterministic laws. Here are two examples:

• a constructive property: each random sequence is Borel normal, in the sense that every word of length n over the binary alphabet occurs in the sequence with the exact expected probability, i.e. 2^-n (see Calude []);

• a non-constructive property: in each random sequence at least one of the two symbols 0 and 1 must occur in arithmetical progressions of every length (see van der Waerden []).

With reference to normality, in a random sequence each bit has, in the long run, a ``mysterious", purely deterministic, influence on all digits. This ``effect" can be tested (of course, only on finite initial segments of the sequence); it can be proven ``from outside", i.e. at the level of the meta-language, and it is ``un-reachable" for any observer from ``inside".

A language-theoretic version of the EPR effect is related to the so-called depth hypothesis. Psychologists have measured the ``span of immediate memory", i.e. the ability to memorize at a glance and repeat correctly random digits, nonsense words, various items. It seems that the average ability is about seven (cf. Miller []). The depth hypothesis suggests that much of the syntactic complexity of a natural language can be understood in terms of this memory restriction.<sup>33</sup> From a mathematical point of view this restriction can be modeled by the property of projectivity (cf. Marcus []) which, in a sense, measures the ``long run" syntactic subordination of words in natural languages. Again, the depth hypothesis, and more generally, any syntactic subordination, is ``visible" from ``outside" and not from ``inside".

4  Conclusions and Further Work

Acknowledgment

References

[]

Ballentine, L. E. The statistical interpretation of quantum mechanics. Reviews of Modern Physics 42 (1970), 358-381.

[]

Bavel, Z., and Muller, D. E. Connectivity and reversibility in automata. J. Assoc. Comput. Mach. 17 (1970), 231-240.

[]

Bell, J. S. Against ``Measurement''. Physics World 3 (1990).

[]

Bell, J. S. Against ``Measurement''. Physikalische Blätter 48, 4 (1992).

[]

Bennett, C. H. Logical reversibility of computation. IBM Journal of Research and Development 17 (1973), 525-532. Reprinted in [].

[]

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

[]

Bennett, C. H., and Landauer, R. The fundamental limits of computation. Scientific American July (1985), 48-56.

[]

Bohr, N. The quantum postulate and the recent development of atomistic theory. Nature 121 (1928), 580-590. Reprinted in [] and in [].

[]

Bohr, N. Atomic Theory and the Description of Nature. Cambridge University Press, London, 1961.

[]

Brauer, W. Automatentheorie. Teubner, Stuttgart, 1984.

[]

Bridgman, P. W. A physicists second reaction to Mengenlehre. Scripta Mathematica 2 (1934), 101-117, 224-234. Cf. R. Landauer [].

[]

Calude, C. Information and Randomness-An Algorithmic Perspective. Springer, Berlin, 1994.

[]

Chaitin, G. J. An improvement on a theorem by E. F. Moore. IEEE Transactions on Electronic Computers EC-14 (1965), 466-467.

[]

Chaitin, G. J. Algorithmic Information Theory. Cambridge University Press, Cambridge, 1987.

[]

Chaitin, G. J. Information, Randomness and Incompleteness, second ed. World Scientific, Singapore, 1990. This is a collection of G. Chaitin's publications.

[]

Clifford, A. H., and Preston, G. B. The Algebraic Theory of Semigroups, vol. 1-2. American Mathematical Society, Providence, 1961.

[]

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

[]

Conway, J. H. Regular Algebra and Finite Machines. Chapman and Hall Ltd., London, 1971.

[]

Dicke, R. H. Interaction-free quantum measurements: A paradox? American Journal of Physics 49, 10 (1981), 925-930.

[]

Dvureenskij, A., Pulmannová, S., and Svozil, K. Partition logics, orthoalgebras and automata. Helvetica Physica Acta 68 (1995), 407-428.

[]

Einstein, A., Podolsky, B., and Rosen, N. Can quantum-mechanical description of physical reality be considered complete? Physical Review 47 (1935), 777-780. Reprinted in [].

[]

Elitzur, A. C., and Vaidman, L. Quantum mechanical interaction-free measurements. Foundations of Physics 23 (1993), 987-997.

[]

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

[]

Foulis, D. J., and Randall, C. Operational statistics. i. basic concepts. Journal of Mathematical Physics 13 (1972), 1667-1675.

[]

Fredkin, E., and Toffoli, T. Conservative logic. International Journal of Theoretical Physics 21 (1982), 219-253.

[]

Gabor, D. Light and information. Progress in Optics 1 (1961), 111-153.

[]

Gécseg, F., and Peák, I. Algebraic Theory of Automata. Akademiai Kiado, Budapest, 1972.

[]

Gill, A. State-identification experiments in finite automata. Information and Control 4 (1961), 132-154.

[]

Ginsburg, S. On the length of the smallest uniform experiment which distinguishes the terminal states of the machine. Journal of the Association for Computing Machinery 5 (1958), 266-280.

[]

Giuntini, R. Quantum Logic and Hidden Variables. BI Wissenschaftsverlag, Mannheim, 1991.

[]

Greenberger, D. B., Horne, M., and Zeilinger, A. Multiparticle interferometry and the superposition principle. Physics Today 46 (August 1993), 22-29.

[]

Greenberger, D. B., and YaSin, A. ``Haunted'' measurements in quantum theory. Foundation of Physics 19, 6 (1989), 679-704.

[]

Grib, A. A., and Zapatrin, R. R. Automata simulating quantum logics. International Journal of Theoretical Physics 29, 2 (1990), 113-123.

[]

Grib, A. A., and Zapatrin, R. R. Macroscopic realization of quantum logics. International Journal of Theoretical Physics 31, 9 (1992), 1669-1687.

[]

Hopcroft, J. E., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979.

[]

Jammer, M. The Conceptual Development of Quantum Mechanics. McGraw-Hill Book Company, New York, 1966.

[]

Jammer, M. The Philosophy of Quantum Mechanics. John Wiley & Sons, New York, 1974.

[]

Jürgensen, H., 1996. private communication.

[]

Kochen, S., and Specker, E. P. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics 17, 1 (1967), 59-87. Reprinted in [].

[]

Kwiat, P., Weinfurter, H., Herzog, T., Zeilinger, A., and Kasevich, M. A. Interaction-free measurement. Physical Review Letters 74 (1995), 4763-4766.

[]

Landauer, R. Irreversibility and heat generation in the computing process. In IBM Journal of Research and Development [], pp. 183-191. Reprinted in [].

[]

Landauer, R. Dissipation and noise immunity in computation and communication. Nature 335 (1988), 779-784.

[]

Landauer, R. Computation, measurement, communication and energy dissipation. In Selected Topics in Signal Processing, S. Haykin, Ed. Prentice Hall, Englewood Cliffs, NJ, 1989, p. 18.

[]

Landauer, R. Advertisement for a paper I like. In On Limits, J. L. Casti and J. F. Traub, Eds. Santa Fe Institute Report 94-10-056, Santa Fe, NM, 1994, p. 39.

[]

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

[]

Marcus, S. Algebraic Linguistics; Analytical Models. Academic Press, New York, 1967.

[]

Mermin, N. D. Hidden variables and the two theorems of John Bell. Reviews of Modern Physics 65 (1993), 803-815.

[]

Messiah, A. Quantum Mechanics, vol. I. North-Holland, Amsterdam, 1961.

[]

Miller, G. A. The magical number seven, plus or minus two: Social limits on our capacity for processing information. The Psychological Review 63 (1956), 81-97.

[]

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

[]

Pauli, W. Die allgemeinen Prinzipien der Wellenmechanik. In Handbuch der Physik (Berlin, 1933), H. Geiger and K. Scheel, Eds., vol. 24, Springer, p. 126. English translation in [] and in [].

[]

Pauli, W. Principles of quantum theory. In Encyclopadia of Physics (Berlin and Göttingen, 1958), S. Flügge, Ed., vol. 5, Springer, pp. 45-46.

[]

Pauli, W. Collected Scientific Papers, vol. I. Interscience, New York, 1964. R. Kronig and Viktor F. Weisskopf.

[]

Penrose, R. The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford University Press, Oxford, 1990.

[]

Penrose, R. Shadows of the Minds, A Search for the Missing Science of Consciouness. Oxford University Press, Oxford, 1994.

[]

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

[]

Prigogine, I. From Being to Becoming. W. H.  Freeman, San Francisco, 1980.

[]

Prigogine, I., and Stengers, I. Order out of Chaos. Bantam Books, Toronto, 1984.

[]

Rössler, O. E. Endophysics. In Real Brains, Artificial Minds, J. L. Casti and A. Karlquist, Eds. North-Holland, New York, 1987, p. 25.

[]

Rössler, O. E. Endophysics, Die Welt des inneren Beobachters. Merwe Verlag, Berlin, 1992. With a foreword by Peter Weibel.

[]

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.

[]

Specker, E. Selecta. Birkhäuser Verlag, Basel, 1990.

[]

Svozil, K. Connections between deviations from lorentz transformation and relativistic energy-momentum relation. Europhysics Letters 2 (1986), 83-85.

[]

Svozil, K. Operational perception of space-time coordinates in a quantum medium. Il Nuovo Cimento 96B (1986), 127-139.

[]

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

[]

Svozil, K. Extrinsic-intrinsec concept and complementarity. In Inside versus Outside, H. Atmanspacker and G. J. Dalenoort, Eds. Springer-Verlag, Heidelberg, 1994, pp. 273-288.

[]

Svozil, K., and Tkadlec, J. Greechie diagrams, nonexistence of measures in quantum logics and Kochen-Specker type constructions. Journal of Mathematical Physics 37, 11 (November 1996), 5380-5401.

[]

Svozil, K., and Zapatrin, R. R. Empirical logic of finite automata: microstatements versus macrostatements. International Journal of Theoretical Physics 35, 7 (1996), 1541-1548.

[]

Toffoli, T. The role of the observer in uniform systems. In Applied General Systems Research, G. Klir, Ed. Plenum Press, New York, London, 1978.

[]

Vaidman, L. On the realization of interaction-free measurements. Quantum Optics 6 (1994), 119-126.

[]

van der Waerden, B. L. Beweis einer baudet'schen vermutung. Nieuw Ark. Wisk 15 (1927), 212-216.

[]

Wang, L. J., Zou, X. Y., and Mandel, L. Induced coherence without induced emission. Physical Review A44 (1991), 4614-4622.

[]

Wheeler, J. A. Law without law. In Quantum Theory and Measurement, J. A. Wheeler and W. H. Zurek, Eds. Princeton University Press, Princeton, 1983, pp. 182-213. [].

[]

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

[]

Wigner, E. P. Remarks on the mind-body question. In The Scientist Speculates, I. J. Good, Ed. Heinemann and Basic Books, London and New York, 1961, pp. 284-302. Reprinted in [].

[]

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

[]

Zou, X. Y., Wang, L. J., and Mandel, L. Induced coherence and indistinguishability in optical interference. Physical Review Letters 67, 3 (1991), 318-321.

Footnotes:

¹ This paper has been completed during the visits of the first author at the University of Technology Vienna, and the University of Western Ontario (1995) and of the third and fourth authors at the University of Auckland in (1995-6). The first author has been partially supported by AURC A18/XXXXX/62090/F3414044, 1995. The third author has been partially supported by a travel grant from the Auß eninstitut of the University of Technology Vienna.

² Computer Science Department, The University of Auckland, Private Bag 92109, Auckland, New Zealand, e-mail: cristian@cs.auckland.ac.nz.

³ Computer Science Department, The University of Auckland, Private Bag 92109, Auckland, New Zealand, e-mail: elena@cs.auckland.ac.nz.

⁴ Institut für Theoretische Physik, University of Technology Vienna, Wiedner Hauptstraß e 8-10/136, A-1040 Vienna, Austria, e-mail: svozil@tph.tuwien.ac.at.

⁵ Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7, e-mail: syu@csd.uwo.ca.

⁶ This is often referred to as a state identification experiment.

⁷ For instance, when they described the implications of the equivalence between cause and effect as an ``axiom" for their mathematical model of motion.

⁸ Up to instances where the wave function is reconstructed.

⁹ ``Active science is thus, by definition, extraneous to the idealized, reversible world it is describing", Prigogine and Stengers, [].

¹⁰ More than 40 years ago Einstein had a similar point: irreversibility is an illusion, a subjective impression. There is no irreversibility in the basic laws of physics.

¹¹ Here k is Boltzmann's constant and T is the absolute temperature in Kelvin degrees, so kT » 3 ×10^-21 Joule at room temperature.

¹² As the energy dissipated per irreversible computational operation approaches the limit of ln2 ×kT, the use of reversible operations is likely to become more attractive.

¹³ This may be seen as a parallel to the Church-Turing thesis, relating the informal notion of ``algorithmically computable function'' to the formal term ``recursive function''.

¹⁴ The propositional system obtained from the Moore automaton is the modular lattice L₁₂ []. An exact quantum mechanical analogue has been given by Foulis and Randall []: Consider a device which, from time to time, emits a particle and projects it along a linear scale. We perform two experiments. In experiment A, the observer determines if there is a particle present. If there is not, the observer records the outcome of A as the outcome {4}. If there is, the observer measures its position coordinate x. If x ³ 1, the observer records the outcome {2}, otherwise {3}. A similar procedure applies for experiment B: If there is no particle, the observer records the outcome of B as {4}. If there is, the observer measures the x-component p_x of the particle's momentum. If p_x ³ 1, the observer records the outcome {1,2}, otherwise the outcome {1,3}. Still another quantum mechanical analogue has been proposed by Giuntini []. A pseudo-classical analogue has been proposed by Cohen [] and by Wright [].

¹⁵ A note of precaution. The analogy between automaton logic and quantum logic must be understood on the level of elements of reality. That is, elements of physical reality correspond to equivalence classes of automaton states-they are not necessarily associated with single automaton states. Every equivalence class is characterized by the requirement that all automaton states contained therein respond identically with respect to a particular input-output experiment. To state the same precaution differently: It would be misleading to assume that any automaton state corresponds to a bona fide element of physical reality (though, perhaps, hidden). Because, whereas in models of automaton complementarity it might still be possible to pretend that initially the automaton actually is in a single automaton state, which we just do not know (such a state can be seen if the automaton is ``screwed open''), quantum mechanically this assumption leads to a Kochen-Specker contradiction [,,,].

¹⁶ The terms ``elements of reality", ``properties", and ``observables" will be used as synonyms.

¹⁷ Note that the automaton in Figure 2 is connected, i.e. every two states are linked by some computation.

¹⁸ In particular, this influence cannot be used to send an actual message from a state to the other.

¹⁹ A more detailed discussion will be given in Section 3.

²⁰ An explanation of this fact will be given in Section 2.8.

²¹ Our proof is a language-theoretical one; we have not been able to extend Conway's algebraic method to properties B, C. We will return to this question in the next section when dealing with the complexity of these decision problems.

²² This result was noticed by Conway [], for CI.

²³ It is worth noticing that this is true regardless the size of the alphabet. Indeed, assuming that S has more than two symbols, the following analysis should be completed with one more case: if f(1) ¹ f(2), f(2) ¹ f(3), and f(1) ¹ f(3), then M has C.

²⁴ In general, the shortest word that can distinguish every pair of states in the automaton ({1, 2,¼,n}, d, f) where d(i,0) = i+1, d(i, 1) = i, for 1 £ i £ n-2, d(n-1,0) = n-1, d(n-1,1) = d(n, 0) = d(n, 1) = n, f(i) = 0, 1 £ i £ n-1,  f(n) = 1) has length 2n-5.

²⁵ We next use the classical notation for regular expressions, cf. Hopcroft and Ullman [].

²⁶ This monoid is sometimes called the transition monoid, cf. Clifford and Preston []; for more details on the algebraic theory see also Gécseg and Peák [].

²⁷ If we remove T_e from (T_w)_{w Î S^*} we get a semigroup which has also a very interesting structure; for example, this semigroup may be a group even in case (T_w)_{w Î S^*} is not. For the automaton (suggested to us by Jürgensen []) whose transitions are given by the following table:

one has T₀₁ = T₁₀ = T₁ and T₀₀ = T₁₁ = T₀. Consequently,

(T_u)_{u Î S^*\{e}} is a group, but none of the generators T₀, T₁ is injective.

²⁸ As each operator is a function from the finite set Q into itself, it follows that an operator T_s is bijective iff it is injective iff it is surjective.

²⁹ Bennett has used a similar strategy for avoiding a huge memory overhead in reversible computations [].

³⁰ Condition G3) was used as a definition for ``reversibility" by Bavel and Muller []; it seems to us to be too strong.

³¹ Sample programs can be obtained from the second author.

³² At this stage no attempt has been made to distinguish between ``isomorphic automata".

³³ The syntax of English, for instance, has many devices for keeping utterances within the bounds of this restriction; it has also resources to circumvent it, as to regain the loss of expressive power.