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 ``selfreferential" 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 tradeoffs 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 fourstates Moore automata.
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 ``interactionfree wave function collapse'' associated with ``interactionfree'' measurement schemes have got renewed attention [,,,]. Compare Bohr's statement (cf. [], reprinted in [])
with Gabor's statement [],¼ 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 coordinates 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.
Indeed, ``interactionfree'' 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 [],No observation can be made with less than one quantum passing through the observed object.
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 complementaryWhat 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.
in the sense that any experimental setup for measuring one object interferes destructively with any experimental setup for measuring the other object [].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 rootmean 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.
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 [].
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:
Figure 1.
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 [].
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 manytoone 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 socalled ``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.

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



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}
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:
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 nonequivalent concepts of computational complementarity based upon modeling finite automata. Informally, they can be expressed as follows. Consider the class of all elements of reality^{16} 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}
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:
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 ZouWangMandel 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.
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¢.
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:
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^{20} 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?
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

Accordingly, for p Î Q and (s_{1}, t_{1})(s_{2}, t_{2}) ¼(s_{n}, t_{n}) Î (S^{2})^{*},


We claim that for every states p,q Î Q,
p,q are distinguishable iff L(M_{p}) ¹ L(M_{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_{1} ¼s_{n} and E(p,w) = t_{1}t_{2} ¼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_{1}, t_{1})(s_{2}, t_{2}) ¼(s_{n}, t_{n}), and w = s_{1} s_{2} ¼s_{n1}. From hypothesis, E(p,w) = t_{1} ¼t_{n} (a Î L(M_{p})), but E(q, w) ¹ t_{1} ¼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
A is true iff L(M_{p}) ¹ L(M_{q}), for all p,q Î Q, p ¹ q.
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:

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}
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}
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.
Figure 4.
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.^{27} Here is the mathematical justification.
The following three statements are equivalent:
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_{u[`u]} = T_{e}. Indeed, if u = s_{1} s_{2}¼s_{n}, then [`u] = x_{sn} ¼x_{s1} does the job. Now take p = T_{[`u]u}(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_{[`w]}. If M has A, then for each pair of distinct states q, q¢ there exists a word w_{q,q¢} such that E(q, w_{q,q¢}) ¹ E(q¢, w_{q,q¢}). To get an experiment which globally distinguishes between any two distinct states we proceed as follows: we concatenate all words w_{q,q¢}[`(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.^{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 multiautomaton 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 metalevel, 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.
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 fourstates automata show that each automaton satisfying CI or CII has a noncommutative monoid of operators. In physical terms, noncommutativity is a mathematical form of complementarity, meaning that ``there is no state in which both measurables have welldefined 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.
Recall that the automaton (Q, d, f) was termed reversible^{30} 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:
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_{1} ¼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^{31}
show that out of 359,040^{32} reversible
fourstates automata:
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:
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  T_{e}  T_{0}  T_{1}  T_{00}  T_{01}  T_{10}  T_{11}  T_{001} 
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:
°  T_{e}  T_{0}  T_{1}  T_{00}  T_{01}  T_{10}  T_{11}  T_{001} 
T_{e}  T_{e}  T_{0}  T_{1}  T_{00}  T_{01}  T_{10}  T_{11}  T_{001} 
T_{0}  T_{0}  T_{00}  T_{01}  T_{00}  T_{001}  T_{10}  T_{11}  T_{001} 
T_{1}  T_{1}  T_{10}  T_{11}  T_{00}  T_{11}  T_{10}  T_{11}  T_{001} 
T_{00}  T_{00}  T_{00}  T_{001}  T_{00}  T_{001}  T_{10}  T_{11}  T_{001} 
T_{01}  T_{01}  T_{10}  T_{11}  T_{00}  T_{11}  T_{10}  T_{11}  T_{001} 
T_{10}  T_{10}  T_{00}  T_{11}  T_{00}  T_{001}  T_{10}  T_{11}  T_{001} 
T_{11}  T_{11}  T_{10}  T_{11}  T_{00}  T_{11}  T_{10}  T_{11}  T_{001} 
T_{001}  T_{001}  T_{10}  T_{11}  T_{00}  T_{11}  T_{10}  T_{11}  T_{001} 
The automaton in Figure 6 satisfies CII:
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  T_{e}  T_{0}  T_{1}  T_{00}  T_{01}  T_{10}  T_{11}  T_{011}  T_{100} 
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:
°  T_{e}  T_{0}  T_{1}  T_{00}  T_{01}  T_{10}  T_{11}  T_{011}  T_{100} 
T_{e}  T_{e}  T_{0}  T_{1}  T_{00}  T_{01}  T_{10}  T_{11}  T_{011}  T_{100} 
T_{0}  T_{0}  T_{00}  T_{01}  T_{0}  T_{01}  T_{10}  T_{011}  T_{011}  T_{100} 
T_{1}  T_{1}  T_{10}  T_{11}  T_{100}  T_{01}  T_{10}  T_{1}  T_{011}  T_{100} 
T_{00}  T_{00}  T_{0}  T_{01}  T_{00}  T_{01}  T_{10}  T_{011}  T_{011}  T_{100} 
T_{01}  T_{01}  T_{10}  T_{011}  T_{100}  T_{01}  T_{10}  T_{01}  T_{011}  T_{100} 
T_{10}  T_{10}  T_{100}  T_{01}  T_{10}  T_{01}  T_{10}  T_{011}  T_{011}  T_{100} 
T_{11}  T_{11}  T_{10}  T_{1}  T_{100}  T_{01}  T_{10}  T_{11}  T_{011}  T_{100} 
T_{011}  T_{011}  T_{10}  T_{01}  T_{100}  T_{01}  T_{10}  T_{011}  T_{011}  T_{100} 
T_{100}  T_{100}  T_{10}  T_{01}  T_{100}  T_{01}  T_{10}  T_{011}  T_{011}  T_{100} 
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):
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):
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
if w = 0^{n}, for some n ³ 1, then 1 and 3 cannot be distinguished: E(1, O^{n}) = 0^{n+1} = E(3, O^{n});
if w = 0^{3n}1y, for some y Î S^{*}, n ³ 1, then 3 and 4 cannot be distinguished: E(1, O^{3n}1) = 0^{3n+2} = E(4, O^{3n}1) and [`(d)](3, 0^{3n}1y) = [`(d)](3, 1y) = [`(d)](1,y) = [`(d)](4, 1y) = [`(d)](4, 0^{3n}1y);
if w = 0^{3n}01y, for some y Î S^{*}, n ³ 1, then 1 and 3 cannot be distinguished: E(1, O^{3n}01) = 0^{3n+3} = E(4, O^{3n}01) and [`(d)](1, 0^{3n}01y) = [`(d)](1, 01y) = [`(d)](1,y) = [`(d)](3, 01y) = [`(d)](3, 0^{3n}01y);
if w = 0^{3n}001y, for some y Î S^{*}, n ³ 1, then 1 and 4 cannot be distinguished: E(1, O^{3n}001) = 0^{3n+4} = E(1, O^{3n}001) and [`(d)](1, 0^{3n}001y) = [`(d)](1, 001y) = [`(d)](1,y) = [`(d)](4, 001y) = [`(d)](4, 0^{3n}001y).
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:
if w = 0^{n}, for some n ³ 1, then 1 and 2 cannot be distinguished: E(1, O^{n}) = 0^{n+1} = E(2, O^{n}), [`(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^{3n}1y, for some y Î S^{*}, n ³ 1, then 1 and 2 cannot be distinguished: E(1, O^{3n}1) = 0^{3n+2} = E(2, O^{3n}1) and [`(d)](1, 0^{3n}1y) = [`(d)](3, 1y) = [`(d)](3,y) = [`(d)](2, 1y) = [`(d)](2, 0^{3n}1y);
if w = 0^{3n}01y, for some y Î S^{*}, n ³ 1, then 2 and 4 cannot be distinguished: E(2, O^{3n}01) = 0^{3n+3} = E(4, O^{3n}01) and [`(d)](2, 0^{3n}01y) = [`(d)](2, 01y) = [`(d)](3,y) = [`(d)](4, 01y) = [`(d)](4, 0^{3n}01y);
if w = 0^{3n}001y, for some y Î S^{*}, n ³ 1, then 1 and 4 cannot be distinguished: E(1, O^{3n}001) = 0^{3n+4} = E(1, O^{3n}001) and [`(d)](1, 0^{3n}001y) = [`(d)](1, 001y) = [`(d)](3,y) = [`(d)](4, 001y) = [`(d)](4, 0^{3n}001y).
In case of nonreversible 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.
Figure 10.
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_{0}, T_{1})which are different from the operators
of the automaton from Figure 7,
State  T_{e}  T_{0}  T_{1} 
1  1  1  1 
2  2  2  2 
3  3  2  1 
4  4  2  1 
but their composition tables do coincide.
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 ChaitinMartinLö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 nonconstructive 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 metalanguage, and it is ``unreachable" for any observer from ``inside".
A languagetheoretic version of the EPR effect is related to the socalled 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".
^{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 (19956). 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, email: cristian@cs.auckland.ac.nz.
^{3} Computer Science Department, The University of Auckland, Private Bag 92109, Auckland, New Zealand, email: elena@cs.auckland.ac.nz.
^{4} Institut für Theoretische Physik, University of Technology Vienna, Wiedner Hauptstraß e 810/136, A1040 Vienna, Austria, email: svozil@tph.tuwien.ac.at.
^{5} Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7, email: 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 ChurchTuring 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 L_{12} []. 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 xcomponent 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 pseudoclassical 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 statesthey 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 inputoutput 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 KochenSpecker 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 languagetheoretical 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 £ n2, d(n1,0) = n1, d(n1,1) = d(n, 0) = d(n, 1) = n, f(i) = 0, 1 £ i £ n1, f(n) = 1) has length 2n5.
^{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 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_{01} = T_{10} = T_{1} and T_{00} = T_{11} = T_{0}. Consequently,
(T_{u})_{u Î S*\{e}} is a group, but none of the generators T_{0}, T_{1} is injective.
^{28} 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.
^{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.