The greater context of automata logic might be characterized by the question of how a computer-generated universe, a ``virtual reality,'' is perceived ``from the inside;'' i.e., by intrinsic observers embedded therein [,,,,,,,]. The intrinsic ``virtual physics'' of a computer-generated universe is defined by experiments and theories which are operational in such an environment. At least for finite systems, this approach is equivalent to the investigation of finite automata by input-output experiments. It is not unreasonable to suspect that the class of finite state input-output systems is ``robust'' in the way that reasonable types of automata can be translated into one another (cf. the equivalence between the classes of Moore and Mealy type automata []).
One of the physical goals of such studies is the investigation of attempts to reconstruct quantum physics in a deterministic, i.e., computable (recursive), environment. Admittedly, such attempts via deterministic cryptosystems appear heretic when viewed from some ``folklore'' understanding of quantum mechanics. Yet, computer-generated universes provide a very natural explanation of complementarity and of the non-Boolean structure of experimental propositions in general.
To be more specific, we shall concentrate on the following measurement problem for finite automata. One may ask, ``given a particular finite (Mealy-type) automaton and its description, which propositions about the initial state are experimentally decidable, i.e., decidable by input-output analysis?'' By introducing the concept of a partition logic, which is related to the pasting construction of orthomodular posets, we are able to construct a propositional calculus of the finite automaton, similar to the lattice approach of Birkhoff and von Neumann []. We are able to show that a broad class of orthomodular posets permits a representation as a partition logic and therefore permits a macroscopic and deterministic realization.
Automaton experiments were introduced by Moore in a pioneering paper [], in which similarities between automata and quantum systems have already been discussed. Moore gave the first explicit example of a four-state automaton featuring computional complementaritiy, a term introduced by D. Finkelstein and S. H. Finkelstein []. A further analysis of Moore's theory of experiments is found in Conway [] and Brauer []. There are also some other studies which investigate the connection between automata and quantum systems, but without using the original form of Moore automata. D. Finkelstein and S. H. Finkelstein have studied [] transaction systems; based on this approach, Grip and Zapatrin [] have described macroscopic automata capable of modeling orthomodular lattices; see also Svozil [] and Schaller and Svozil [].
We shall adapt the terminology of Pták and Pulmannová, []. Let a prime ideal be the kernel P = { x Î L\mid s(x) = 0} of a two-valued state s.
Definition 1 [Primeness] An orthomodular poset L is called prime if for all a,b in L and a ¹ b there exists a prime ideal containing exactly one of a and b.
A partition logic can be defined as follows.
Definition 2 [Partition logic] Let M be a set and \frak R be a family of partitions of M. Every partition P Î \frak R generates a Boolean algebra (BP, Í ,¢) in the following way: BP = {ÈS\mid S Í P}. Í is the inclusion and ¢ the complement in M. We will call the pasting of all this Boolean algebras the partition logic of M and \frak R and denote it by (M,\frak R).
[ 1 A partition logic is an orthomodular poset iff the following two conditions hold: (i) the induced relation £ is transitiv; (ii) if a ^b, then the supremum a Úb exists.
Proof. An OMP satisfies conditions (i) and (ii). It is trivial that £ is a partial order and ¢ is a orthocomplement. If a^b than a £ P b for a partition P in \frak R. The supremum is then given by aÚP b = a Èb = aÚb. The orthomodular law holds because for a £ b we have b = a ÚP(a¢ÙP b) = a Ú(a¢Ùb). For a more general statement, see [].
The following theorem is related to the Birkhoff-Stone representation theorem for distributive lattices or Boolean algebras (cf. [] or []) and to the representation theorem of Gudder for concrete logics [].
[ 1 An orthomodular poset L is isomorphic to a partition logic iff L is prime.
Proof. Let the sub-orthomodular poset GA generated by an arbitrary subset A of L be the smallest subalgebra of L containing A. Let \frak C(L) = {G{x,y}\mid x,y Î L and x £ y}. L is the pasting of the family \frak C(L). (i) Suppose first that L is isomorphic to a partition logic (M,\frak R). We may assume that L = (M,\frak R). Take A,B Î L such that A ¹ B. Then C = (A - B) È(B - A) ¹ Æ and we can choose a point p Î C. We define P = { X Î L\mid p \not Î X}. It is easy to check that P is a prime ideal. Finally, either p Î A or p Î B, which means that L is prime.
(ii) Let L be a prime orthomodular poset. Consider the mapping p: L ® \frak P(P(L)),p(a) = {P Î P(L)\mid a \not Î P }. Let M = P(L) and G Î \frak C (L). Define a partition RG of P(L) by RG = {p(a)\mid a is atom of G}. RG is indeed a partition, because p(a Úb) = p(a) Èp(b) holds for a ^b and moreover, p(a¢) = P(L) - p(a) = p(a)¢. Put \frak R = {RG\mid G Î \frak C(L)} and let R be the partition logic (M,\frak R). We propose, that p: L ® R is an isomorphism. p is injective by the primeness of L, p is surjective by the construction of R. For every G Î \frak C(L) the restriction of p to G, p\midG: G® RG, is an isomorphism. Since L is the pasting of \frak C(L) and R is the pasting of \frak R, L and R are also isomorphic.
[ 2 Every concrete logic is a partition logic.
Proof. We prove that every rich orthomodular poset is prime. Let L be a rich orthomodular poset. We set P(x) = {P Î P(L)|x \not Î P} for all x Î L. Let a,b be two arbitrary elements of L. If P(a) = P(b) then a = b by the richness of L. Hence, for a ¹ b the set (P(a) - P(b)) È(P(b) - P(a)) is not empty and therefore L is prime.
As the non-rich [] Greechie logic of Fig. shows, the inverse does not hold; i.e., not every partition logic is rich.
Picture Omitted
Consider a Mealy automaton. Assume its formal description is given but the initial state is unknown. Further, we are not allowed to open the automaton and look inside, i.e. we consider the automaton as a black box with interfaces for the input and output of symbols. Hence, to gain information about the initial state we have to enter some input and observe the output. We are interested in which propositions about the initial state are decidable by input-output-analysis.
Definition 3 [(Mealy) automaton]
A Mealy automaton is a 5-tuple M = (Q,S,D,d,l),
where
l(q,a1)l(d(q,a1),a2)l(d(d(q,a1),a2),a3)¼l(d(¼,an-1),an) Î D*.
We represent automata by a directed graph, called the transition diagram.
The vertices of the graph correspond to the states of the automaton.
An arc labeled x/y from vertice p to vertice q stands for
d(p,x) = q and l(p,x) = y.
(i) Q is the set of states;
(ii) S is the input alphabet;
(iii) D is the output alphabet;
(iv) d:Q×S® Q is the transition
function;
(v) l:Q×S® D is the output
function.
At any time the automaton is in a state q Î Q.
If the automaton receives an input symbol a Î S,
M enters the state d(q,a) and emits the
output l(q,a).
An input (resp. output) word is a (possible empty) formal sequence
of input (resp. output) symbols.
S* (resp. D*) denotes the set of all input (resp.
output) words.
The empty word is denoted by e.
The output of an input word a1 ¼an Î S*
is therefore the word
A branch experiment can be described by a mapping E:D* ® SÈ{e}. The branch experiment E is carried out in the following way: (i) E(e) denotes the initial input symbol. (ii) Let us assume the input w Î S* was applied and the output W Î D* was observed. Then we enter the input E(W) into the automaton. The experiment terminates if E(W) = e. lE(q) denotes the observed output, if the automaton was in the initial state q. A subset of the branch experiments are the preset experiments. An input word w Î S* is applied to the automaton and the output is observed.
We identify propositions about the inital state with subsets of Q. To every state q Î Q we assign the proposition, that the intial state of the automaton is q and write for this propostion again q. In the same way, we identify a subset P of Q with the proposition that the inital state is in P. We call a proposition experimentally decidable if there is an experiment which determines the true value of the proposition.
Definition 4 [Automaton logic]
To every experiment, E defines an equivalence relation
= in Q by
p = q if lE(p) = lE(q).
The partition corresponding to = is denoted by
Q/E and the Boolean algebra induced by Q/E by BE.
The propositions decidable by the experiment E are the
elements of BE.
The automaton propositional calculus
(automaton logic) is defined as the partition logic (Q,\frak B),
where
\frak B denotes the set of all Boolean algebras BE.
The orthocomplement P¢ of a proposition P, i.e. the set complement
Q - P, denotes the logical negation of P.
Every experiment which decides P also decides P¢.
The relation P1 £ P2 holds iff
(i) P1 Í P2, i.e if P1 implies P2 and
(ii) there is an experiment which decides both propositions P1 and
P2.
Note that £ is not an idealistic relation, but a measurable one.
We illustrate the construction of the automaton propositional calculus by an example. The Mealy-type automaton of Fig. .a) is modeled after Moore's uncertainty automaton.
Picture Omitted
Picture Omitted
The simple experiment 0, i.e the input of 0, yields the partition Q/0 = {{1,3},{2},{4}}. The simple experiment 1, i.e the input of 1, yields the partition Q/1 = {{1,2},{3},{4}}. Obviously there are no finer partitions accessible by experiments. (The trivial partition
Q/e = {{1,2,3,4}} corresponds to no input/output experiment.) Note that the proposition 1 is not experimentally decidable. The propositional calculus is given in Fig. .a). It is isomorphic to a finite sublattice of the quantum logic of the threedimensional Hilbert space. The automaton defined by Fig. 2.b) yields a propositional calculus drawn in Fig. .b), which is also found in the quantum logic of a twodimensional Hilbert space.
Picture Omitted
Picture Omitted
A straightforward construction [] shows that to every partition logic there exists an automaton which posesses that partition logic as propositional calculus and vice versa.
[ 3 [Automaton logic = partition logic] Every automaton proposition calculus is a partition logic and vice versa.
We have already remarked that not every partition logic is an orthomodular poset. An automaton example for this case is given in Fig. .
Picture Omitted
The finest partition accessible by experiments are Q/00 = {{1},{2},{3,4}} and Q/10 = {{1,2},{3},{4}}. If we consider the partition logic of this two partitions {1} £ {1,2} and {1,2} £ {1,2,3} holds, but not {1} £ {1,2,3}.
Conversely, not every orthomodular poset corresponds to a partition logic. Consider the Greechie diagram of W3,4 drawn in Fig. . It is an orthomodular poset, since it does not contain any loop of order three. Consider Fig. . In these figures the bold lines indicate a disjoint covering of L by its blocks. In Fig. .a) the covering consists of 3 blocks B1,B2 and B3. In Fig. .b) there is a disjoint covering consisting of 4 blocks Ba,Bb,Bc and Bd. Assume that the orthomodular poset is isomorphic to a partition logic (M,\frak R). Let x Î M. x has to be element in one of the atoms of Ba. Without loss of generality one may assume that x Î a1. x has also to be element in one of the atoms of Bb. Since x Î a1, x Î a2 is not possible, because a1,a2 are atoms of the same block B1. Without loss of generality one may assume that x Î a6. x has also to be element in one of the atoms of Bc. The only choice left is x Î a11. x has also to be element in one of the atoms of Bd. But every choice x Î a4,x Î a8 or x Î a12 is in contradiction to x Î a1,x Î a6 and x Î a11, respectively. Therefore, the orthomodular poset is not isomorphic to a partition logic.
Picture Omitted
Furthermore, there exist orthomodular lattices which do not correspond to any partition logic. A typical Example is the ``spider'' lattice; cf. Pták and Pulmannová, [], p. 37.
We have formally characterized the propositional systems of a general class of automata called Mealy automata. The class of Mealy automata is equivalent to the class of Moore automata [,] (upon disregarding the first output symbol). It is sufficiently complex to embody even more general types of discrete deterministic input/output systems. In this sense it is robust.
Any prime orthomodular lattice allowing two-valued states can be represented by a partition logic derived from this class of Mealy- (Moore-) type automata.
Is it possible to reconstruct quantum logic by the partition logic of automata? We find that quantum and automaton logic as they are defined here do not coincide completely, but they ``overlap.'' To demonstrate this, consider particular finite orthomodular sublattices of quantum mechanical Hilbert lattices. For example, for 2-dimensional Hilbert spaces, automaton logics which are of the general form MOn [e.g., MO3 is drawn in Fig. 3.b)] correspond to all finite sublogics of the logic L(H). However, since L(H) is undenumerable, automaton logics can never model the complete quantum logic even in the twodimensional case.
For dimensions higher than or equal to three, it can be inferred from Gleason's theorem that the orthomodular poset L(H) for dim H ³ 3 does not posess any two-valued state and therefore does not posess any prime ideal (cf. [], p. 23). Therefore, as for the twodimensional case, the entire L(H),
dimH ³ 3 is not representable as partition logic. Nevertheless, certain sub-orthomodular posets of the threedimensional Hilbert lattice are reprensentable by automaton logic. For example, as can be verified by considering Fig. (cf [], p. 160), the
Picture Omitted
lattice drawn in Fig. 3.a) is a sub-orthomodular poset of L(H), dim H = 3, leaving the question open whether all finite sub-orthomodular posets of quantum logics are reprensentable by partition logics of automata [].
154, 157-168 (1991).