Physical versus Computational Complementarity I1

Cristian Calude,2     Elena Calude,3     Karl Svozil,4     Sheng Yu5

Abstract

The dichotomy between endophysical/intrinsic and exophysical/extrinsic perception concerns the question of how a model-mathematical, logical, computational-universe is perceived from inside or from outside, [,,,,,,]. This distinction goes back in time at least to Archimedes, reported to have asked for a point outside the world from which one could move the earth. An exophysical perception is realized when the system is laid out and the experimenter peeps at the relevant features without changing the system. The information flows on a one-way road: from the system to the experimenter. An endophysical perception can be realized when the experimenter is part of the system under observation. In such a case one has a two-way informational flow; measurements and entities measured are interchangeable and any attempt to distinguish between them ends up as a convention.

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

This section is mainly expository: we will present the physical and mathematical contexts for our work.

1.1  Physical Complementarity

Relativity altered the classical concept of physical objectivity but left open the possibility of a supreme mathematician who, in Einstein's view, neither cheats nor plays dice. Quantum mechanics goes one step further: it not only does situate the experimenter in the universe, but it states that the experimenter can be modeled as a ``sturdy, classical entity" composed of a macroscopic number of microscopic objects. Nevertheless, the experimenter can neither predict nor control certain ``spontaneous" microphysical events. Moreover, the observer is bound by complementarity-that is, informally speaking, either experiences one certain type of observation, (exclusive) or a different, complementary one.

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.

with Gabor's statement [],

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

Indeed, ``interaction-free'' measurement schemes suggest that it is no longer necessary to assume that any measurement has to be associated with the exchange of at least one quantum of action. The situation seems to conform more to an issue raised by Landauer [],

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.

The ``folklore'' understanding of complementarity, in general, and the Heisenberg uncertainty relation, in particular, is the existence of certain (complementary) features of a quantum system which cannot be measured and predicted simultaneously with arbitrary accuracy. The first (but not last) attempt to overcome a certain vagueness in its definition [] has been undertaken by Pauli [], who called two classical concepts complementary

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)

in the sense that any experimental setup for measuring one object interferes destructively with any experimental setup for measuring the other object [].

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

Moore [] has studied some experiments on finite deterministic automata trying to understand what kind of conclusions about the internal conditions of a finite machine it is possible to draw from input-output experiments. To emphasize the conceptual nature of his experiments, Moore has borrowed from physics the word ``Gedanken".

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".6

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:


d
 
(q, e ) = q , for all q Q,

d
 
(q, sw) =
d
 
(d(q,s),w), for all q Q, s S, w S* .

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

E: Q ×S* S*
defined as follows:
E(q, e) = f(q),
E(q, sw) = f(q) E(d(q,s),w)), q Q, s S, w S*,
and f: Q S is the output 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



q s d(q, s)
1 0 4
1 1 3
2 0 1
2 1 3
q s d(q, s)
3 0 4
3 1 4
4 0 2
4 1 2



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:



1.00mm
Picture Omitted

           Figure 1.



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

E(1, 000100010) = f(1) f(4)f(2) f(1) f(3) f(4) f(2) f(1) f(3)f(4) = 0100010001.

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

Everyone is familiar with the strange effects produced by projecting a film backward. This ``strangeness" is considered to be normal in classical dynamics, as was explicitly stated by its founders Galileo or Huygens.7 Quantum mechanics, in which state preparations and measurements are irreversible8, raised serious doubts related to reversibility and initiated the abolition of it.9

A new perspective on this issue came recently from computation theory.10 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.11

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

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* 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

Consider now a Moore's automaton M = (Q, d, f). Following Moore [] we shall say that a state q is ``indistinguishable" from a state q (with respect to M) if every experiment performed on M starting in state q produces the same outcome as it would starting in state q. Formally,
E(q , x) = E(q, x),
for all words x S+.

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

f(
d
 
(q, w)) = f(
d
 
(q, w)).
Indeed,
E(q, x1 x2 xn) = f(q) f(
d
 
(q, x1)) f(
d
 
(q, x1 x2))f(
d
 
(q, x1 x2 xn)),   q Q, x1x2 xn 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

E(1, x) = E(1, 1u) = f(1) f(d(1, 1))E(d(1, 1), u) = f(1)f(3)E(3, u) = 00E(3, u)
and
E(2, x) = E(2, 1u) = f(2)f(d(2, 1))E(d(2, 1), u) = f(2)f(3)E(3, u) = 00E(3, u).

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

E(1, x) = E(2, x),
that is x cannot distinguish between the states 1, 3 as
E(1, x) = E(1, 0v) = f(1)f(d(1, 0))E(d(1, 0), v) = f(1)f(4)E(4, v) = 01E(4, v)
and
E(3, x) = E(3, 0v) = f(3)f(d(3, 0))E(d(3, 0), v) = f(3)f(4)E(4, v) = 01E(4, v).

2.2  Computational Complementarity

The difficulties in understanding and conceptualizing the complementarity phenomenon served as a motivation for considering extremely simple models featuring complementarity.13

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:14

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

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 reality16 and consider the following properties.

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

1.00mm
Picture Omitted

           Figure 2.



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:

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 wq (depending upon q) such that E(q, wq ) E(q, wq ), 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.18 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. 19

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

Of course, C implies B, which, in turn, implies A; none of the converse implications is true. Moore's automaton (see Figure 1) has A but non-B. The following automaton has B but non-C:



1.00mm
Picture Omitted

       Figure 3.



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:

The above example, though easy to deal with, is not very interesting20 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.21

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

Mq = (Q {#}, S×S, q, d, Q),
with initial state q and final states Q; here # is a new symbol added to Q. The transition function d is defined as follows: d(p, (s, t)) = d(p, s) in case f(p) = t, and d(p, (s, t)) = #, otherwise. Here p Q {#} and s, t S.

Accordingly, for p Q and (s1, t1)(s2, t2) (sn, tn) (S2)*,


d
 
(p, (s1, t1)(s2, t2) (sn, tn)) # iff E(p, s1 s2 sn-1) = t1 t2 tn-1 tn,
and in case the above condition holds true


d
 
(p, (s1, t1)(s2, t2) (sn, tn)) =
d
 
(p, s1 s2 sn).

We claim that for every states p,q Q,

p,q are distinguishable iff L(Mp) L(Mq).

Assume first that p and q are distinguishable, that is, there exists w S+ such that E(p,w) E(q,w). Let w = s1 sn and E(p,w) = t1t2 tn+1. Take an arbitrary letter sn+1 S and put

a = (s1, t1)(s2, t2) (sn, tn)(sn+1,tn+1).
Clearly, a L(Mp) \L(Mq): [`(d)](p, a) = [`(d)](p, w)   (E(p,w) = t1t2 tn+1), but [`(d)](q, a) = #   (E(p,w) E(q,w)).

Conversely, assume that L(Mp) L(Mq). Then, there exists a L(Mp) \L(Mq) (or a L(Mq) \L(Mp)). Let

a = (s1, t1)(s2, t2) (sn, tn), and w = s1 s2 sn-1. From hypothesis, E(p,w) = t1 tn   (a L(Mp)), but E(q, w) t1 tn   (a\not L(Mq)), 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

A is true iff L(Mp) L(Mq), for all p,q Q, p q.

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

S(q) =

p Q, p q 
((L(Mq) \L(Mp))(L(Mp) \L(Mq))).

As the problem of testing whether L(Mp) L(Mq) is algorithmically decidable, it follows that A is decidable.

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

Dp,q = (L(Mp) \L(Mq)) (L(Mq) \L(Mp)),
for all states p, q. Then we notice the equivalence

A is true iff Dp,q , for all p,q Q, p q.

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

S(q) =

p Q, p q 
Dq,p.

Clearly,

B is true iff for every q Q, S(q) .

Finally, the decidability of C follows from the formula:

C is true iff

q Q 
S(q) .

2.4  Complexity Issues

First we note that complementarity properties CI, CII cannot appear for Moore automata with less than four states.22 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:23

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

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:25



0.5mm
Picture Omitted

           Figure 4.



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) Ts: Q Q,   s S,  Ts(q) = d(q, s), as ``push buttons" allowing the automaton to change its states. Mathematically, we shall associate to M a class of operators (Tw)w S*,

Tw : Q Q,   Tw (q) =
d
 
(q,w).
Clearly, for all u,w S*,  Tu Tv = Tuv, so (Tw)w S* is a monoid (Te is the neutral element).26 In fact, this monoid is finite: define the equivalence relation u v if Tu = Tv, pick from each equivalence class the smallest word (in quasi-lexicographical order) and collect all these words into the finite set S. Then each operator Tu has a ``name" Tv with v S.

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



The following three statements are equivalent:

  1. The operators (Tw)w S form a group.
  2. Each operator Ts,  s S is bijective.28
  3. Every operator Ts, 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 xs (depending upon s) such that Tsxs = Te. 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 Tu[`u] = Te. Indeed, if u = s1 s2sn, then [`u] = xsn xs1 does the job. Now take p = T[`u]u(q). As


d
 
(p,
u
 
) =
d
 
(
d
 
(q,
u
 
u),
u
 
) =
d
 
(
d
 
(q,
u
 
), u
u
 
) =
d
 
(q,
u
 
)
it follows that


d
 
(p,
u
 
) =
d
 
(q,
u
 
).

Using again the hypothesis and the above equality we get

p =
d
 
(
d
 
(p,
u
 
),

u
 
 
) =
d
 
(
d
 
(q,
u
 
),

u
 
 
) = q,
which tells us that T[`u] is the inverse of Tu.

Each of the above equivalent conditions G1) - G3) implies the equivalence of A, B and C. Indeed, every operator Tw has an inverse T[`w]. If M has A, then for each pair of distinct states q, q there exists a word wq,q such that E(q, wq,q) E(q, wq,q). To get an experiment which globally distinguishes between any two distinct states we proceed as follows: we concatenate all words wq,q[`(wq,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.29 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 reversible30 if for every states p, q Q and u S* with [`(d)](p,u) = q, then there exists a word w S* 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 vsq S* (depending upon s and q) such that [`(d)](q, svsq) = q.

We have to prove only the equivalence between the last condition and reversibility. Indeed, if u = s1 sn, then


d
 
(q, uvn[`(d)](q,s1 sn-1) v2[`(d)](q,s1) v1q) = q.

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 computations31 show that out of 359,04032 reversible four-states automata:

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

1.00mm
Picture Omitted

           Figure 5.



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:

The monoid of operators has 8 elements



State Te T0 T1 T00 T01 T10 T11 T001
1 1 4 1 2 1 4 1 3
2 2 2 3 2 3 4 1 3
3 3 4 1 2 1 4 1 3
4 4 2 1 2 3 4 1 3



and the induced table is the following:

Te T0 T1 T00 T01 T10 T11 T001
Te Te T0 T1 T00 T01 T10 T11 T001
T0 T0 T00 T01 T00 T001 T10 T11 T001
T1 T1 T10 T11 T00 T11 T10 T11 T001
T00 T00 T00 T001 T00 T001 T10 T11 T001
T01 T01 T10 T11 T00 T11 T10 T11 T001
T10 T10 T00 T11 T00 T001 T10 T11 T001
T11 T11 T10 T11 T00 T11 T10 T11 T001
T001 T001 T10 T11 T00 T11 T10 T11 T001



The automaton in Figure 6 satisfies CII:



1.00mm
Picture Omitted

           Figure 6.



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:

In this case the monoid of operators has 9 elements

State Te T0 T1 T00 T01 T10 T11 T011 T100
1 1 2 4 3 1 2 1 4 3
2 2 3 1 2 1 2 4 4 3
3 3 2 1 3 1 2 4 4 3
4 4 2 1 3 1 2 4 4 3



and the induced table is the following:



Te T0 T1 T00 T01 T10 T11 T011 T100
Te Te T0 T1 T00 T01 T10 T11 T011 T100
T0 T0 T00 T01 T0 T01 T10 T011 T011 T100
T1 T1 T10 T11 T100 T01 T10 T1 T011 T100
T00 T00 T0 T01 T00 T01 T10 T011 T011 T100
T01 T01 T10 T011 T100 T01 T10 T01 T011 T100
T10 T10 T100 T01 T10 T01 T10 T011 T011 T100
T11 T11 T10 T1 T100 T01 T10 T11 T011 T100
T011 T011 T10 T01 T100 T01 T10 T011 T011 T100
T100 T100 T10 T01 T100 T01 T10 T011 T011 T100



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):



1.00mm
Picture Omitted

           Figure 7.



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):

1.00mm
Picture Omitted

           Figure 8.



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

2.8  More About Moore's Example

The size of Moore's automaton is 64. This automaton can be used with different output functions to produce both CI and CII . The complement of the original output function leads to CI . To get CII we can use each of the output functions in Figure 9:



1.00mm
Picture Omitted
1.00mm
Picture Omitted

           Figure 9.



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:

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.





1.00mm
Picture Omitted

           Figure 10.



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



State Te T0 T1
1 1 1 1
2 2 2 2
3 3 2 1
4 4 1 1

Te T0 T1
Te Te T0 T1
T0 T0 T0 T0
T1 T1 T1 T1



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 (Te, T0, T1)-which are different from the operators of the automaton from Figure 7,



State Te T0 T1
1 1 1 1
2 2 2 2
3 3 2 1
4 4 2 1



but their composition tables do coincide.

3  More About Actors and Spectators

The new type of complementarity, namely CII , introduced in this paper, mimics, in a sense, the state of quantum entanglement and may be conceived as a toy model for the EPR effect or the Zou-Wang-Mandel effect [,,]. Being experimentally testable, CII falls into the class of puzzle mysteries (see Penrose []).

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:

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

Building on Moore's work concerning ``Gedanken" experiments a new type of computational complementarity, which mimics the state of quantum entanglement, was introduced and contrasted with Moore's computational complementarity and physical complementarity. Many problems remain for further work. We mention here only a few of them: 1) Find better upper bounds for testing properties B, C; 2) Describe CI, CII for Mealy automata and for non-deterministic finite automata; 3) Distinguish between isomorphic automata; 4) Investigate the influence of the size of the underlying alphabet; 5) Explore the relations between CI, CII and automata/quantum logics.

Acknowledgment

We express our gratitude to Professors H. Jürgensen, R. Nicolescu, B. Pavlov and S. Rudeanu for their comments and suggestions.

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:

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

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

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

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

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

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

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

8 Up to instances where the wave function is reconstructed.

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

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

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

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

13 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''.

14 The propositional system obtained from the Moore automaton is the modular lattice L12 []. 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 px of the particle's momentum. If px 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 [].

15 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 [,,,].

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

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

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

19 A more detailed discussion will be given in Section 3.

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

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

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

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

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

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

26 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 [].

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



q s d(q, s)
1 0 1
1 1 3
2 0 1
2 1 3
q s d(q, s)
3 0 3
3 1 1
4 0 4
4 1 4



one has T01 = T10 = T1 and T00 = T11 = T0. Consequently,

(Tu)u S*\{e} is a group, but none of the generators T0, T1 is injective.

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

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

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

31 Sample programs can be obtained from the second author.

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

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


File translated from TEX by TTH, version 1.94.
On 9 Sep 1999, 13:33.