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

partition.tex

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
(B _{P}, Í ,¢) in the following way:
B_{P} = {È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 R_{G} of P(L) by
R_{G} = {p(a)\mid a is atom of G}.
R_{G} 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 = {R_{G}\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® R_{G}, 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
(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*

*
l(q,a _{1})l(d(q,a_{1}),a_{2})l(d(d(q,a_{1}),a_{2}),a_{3})¼l(d(¼,a_{n-1}),a_{n}) Î 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.
l_{E}(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 l _{E}(p) = l_{E}(q).
The partition corresponding to = is denoted by
Q/E and the Boolean algebra induced by Q/E by B_{E}.
The propositions decidable by the experiment E are the
elements of B_{E}.
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 B_{E}.
*

*
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 P _{1} £ P_{2} holds iff
(i) P_{1} Í P_{2}, i.e if P_{1} implies P_{2} and
(ii) there is an experiment which decides both propositions P_{1} and
P_{2}.
*

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 W_{3,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 B_{1},B_{2} and
B_{3}.
In Fig. .b) there is a disjoint covering consisting of 4
blocks
B_{a},B_{b},B_{c} and B_{d}.
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 B_{a}.
Without loss of generality one may assume that x Î a_{1}.
x has also to be element in one of the atoms of B_{b}.
Since x Î a_{1}, x Î a_{2} is not possible,
because a_{1},a_{2} are atoms of the same block B_{1}.
Without loss of generality one may assume that x Î a_{6}.
x has also to be element in one of the atoms of B_{c}.
The only choice left is x Î a_{11}.
x has also to be element in one of the atoms of B_{d}.
But every choice x Î a_{4},x Î a_{8} or x Î a_{12} is in
contradiction to x Î a_{1},x Î a_{6} and x Î a_{11}, 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
MO_{n}
[e.g., MO_{3} 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 [].

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

On 9 Sep 1999, 13:46.