[section] definition] Theorem definition]Lemma

Automaton partition logic versus quantum logic

Automaton partition logic versus quantum logic

M. Schaller and K. Svozil
Institut für Theoretische Physik, Technische Universität Wien
Wiedner Hauptstraß e 8-10/136, A-1040 Vienna, Austria
e-mail: svozil@tph.tuwien.ac.at


The propositional system of a general class of discrete deterministic systems is formally characterized. We find that any finite prime orthomodular lattice allowing two-valued states can be represented by an automaton logic.


1  Automaton logic as the experimental logic of virtual realities - a connection to quantum logic

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

2  Partition Logic

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 aP b = a b = ab. The orthomodular law holds because for a b we have b = a P(aP b) = a (ab). 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

Figure 1: Prime orthomodular poset, which is not rich

3  Automaton propositional calculus

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

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.

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

Figure 2: a) Moore's uncertainty automaton, modeled as Mealy automaton; b) quantumlike Mealy automaton

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

Figure 3: a) Hasse diagram of the automaton logic of Moore's uncertainty automaton; b) Hasse diagram of the automaton logic of the quantumlike Mealy automaton

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

Figure 4: Mealy automaton, yielding a nontransitive propositional calculus

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

Figure 5: Orthomodular poset W3,4 which is no automaton logic

Picture Omitted

Figure 6: Disjoint coverings of orthomodular poset which is no automaton logic

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.

4  Discussion

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

Figure 7: Identification of atoms with rays in threedimensional real Hilbert space. If v(a) is the subspace spanned by a, v(12) ^v(3), v(2)^v(13), v(12) ^v(4), v(2) ^v(4), v(3) ^v(4), v(13) ^v(4), v(12) v(2)

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


R. J. Boskovich, De spacio et tempore, ut a nobis cognoscuntur (Vienna, 1755); English translation in A Theory of Natural Philosophy, ed. by J. M. Child (Open Court, Chicago, 1922; reprinted by MIT press, Cambridge, MA, 1966), p. 203-205.

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

O. E. Rössler, Endophysics, in Real Brains, Artificial Minds, ed. by J. L. Casti and A. Karlquist (North-Holland, New York, 1987), p. 25.

O. E. Rössler, Endophysics, Die Welt des inneren Beobachters, ed. by P. Weibel (Merwe Verlag, Berlin, 1992).

K. Svozil, On the setting of scales for space and time in arbitrary quantized media (Lawrence Berkeley Laboratory preprint LBL-16097, May 1983).

K. Svozil, Europhysics Letters 2, 83 (1986).

K. Svozil, Il Nuovo Cimento 96B, 127 (1986).

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

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

G. Birkhoff, Lattice Theory, Second Edition (American Mathematical Society, New York, 1948).

G. Birkhoff and J. von Neumann, Annals of Mathematics 37, 823 (1936).

W. Brauer, Automatentheorie, Stuttgart: Teubner 1984

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

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

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

A. A. Grib and R. R. Zapatrin, International Journal of Theoretical Physics 29, 113-123 (1990); Ibid. 31, 1669-1687 (1992).

S. Gudder, Stochastic Methods in Quantum Mechanics (North-Holland, Amsterdam, 1979).

E. F. Moore, Gedanken-Experiments on Sequential Machines, in Automata Studies, ed. by C. E. Shannon & J. McCarthy (Princeton University Press, Princeton, 1956).

M. Navara and V. Rogalewicz, Math. Nachr.

154, 157-168 (1991).

P. Pták and S. Pulmannová, Orthomodular Structures as Quantum Logics (Kluwer Academic Publishers, Dordrecht, 1991).

K. Svozil, Randomness and Undecidability in Physics (World Scientific, Singapore, 1993).

M. Schaller and K. Svozil, Il Nuovo Cimento 109 B, 167 (1994).

G. Szász, Introduction to Lattice Theory (Academic Press, New York, 1963).

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

This amounts to the following problem, which is the finitistic equivalent to Professor G. Kalmbach's 29th problem on orthomodular lattices [cf. G. Kalmbach, Orthomodular Lattices (Academic Press, New York, 1983), p. 348]: Characterise, lattice-theoretically, the finite orthomodular lattices of closed subspaces of finite dimensional Hilbert lattices.

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