Logical equivalence between generalized urn models and finite automata

Karl Svozil
Institut für Theoretische Physik, University of Technology Vienna
Wiedner Hauptstraße 8-10/136, A-1040 Vienna, Austria
e-mail: svozil@tuwien.ac.at

Abstract

1  Introduction of concepts

In what follows we shall explicitly and constructively demonstrate the equivalence of the empirical logics (i.e., the propositional calculi) associated with the generalized urn models (GUM) suggested by Ron Wright [1,2], and automaton partition logics (APL) [3,4,5,6,7]. (The result has been mentioned already in [7,p.145], but no proof has been given). The logical equivalence of automaton models (AM) with generalized urn models suggests that these logics are more general and ``robust'' with respect to changes of the particular model than could have been expected from the particular instances of their first appearance.

1.1  Generalized urn models

Let |U| be the number of different types of balls, |C| be the number of different mono-spectral colors, |L| be the number of different output symbols.

Consider the deterministic ``output'' or ``lookup'' function L (u,c)=v, u Î U, c Î C, v Î L, which returns one symbol per ball type and color. One interpretation of this lookup function L is as follows. Consider a set of |C| eyeglasses build from filters for the |C| different colors. Let us assume that these mono-spectral filters are ``perfect'' in that they totally absorb light of all other colors but a particular single one. In that way, every color can be associated with a particular eyeglass and vice versa.

When a spectator looks at a particular ball through such an eyeglass, the only operationally recognizable symbol will be the one in the particular color which is transmitted through the eyeglass. All other colors are absorbed, and the symbols printed in them will appear black and therefore cannot be differentiated from the black background. Hence the ball appears to carry a different ``message'' or symbol, depending on the color at which it is viewed.

An empirical logic can be constructed as follows. Consider the set of all ball types. With respect to a particular colored eyeglass, this set disjointly ``decays'' or gets partitioned into those ball types which can be separated by the particular color of the eyeglass. Every such partition of ball types can then be identified with a Boolean algebra whose atoms are the elements of the partition. A pasting of all of these Boolean algebras yields the empirical logic associated with the particular urn model.

1.2  Automaton models

A typical automaton experiment aims at an operational determination of an unknown initial state by the input of some symbolic sequence and the observation of the resulting output symbols. Every such input/output experiment results in a state partition in the following way. Consider a particular automaton. Every experiment on such an automaton which tries to solve the initial state problem is characterized by a set of input/output symbols as a result of the possible input/output sequences for this experiment. Every such distinct set of input/output symbols is associated with a set of initial automaton states which would reproduce that sequence. This state set may contain one or more states, depending on the ability of the experiment to separate different initial automaton states. A partitioning of the automaton states is obtained if one considers a single input sequence and the variety of all possible output sequences (given a particular automaton). Stated differently: given a set of inputs, the set of automaton states decays into disjoint subsets associated with the possible output sequences. (All elements of a subset yield the same output on the same input.)

This partition can then be identified with a Boolean algebra, with the elements of the partition interpreted as atoms. By pasting the Boolean algebras of the ``finest'' partitions together one obtains an empirical partition logic associated with the particular automaton. (The converse construction is also possible, but not unique; see below.)

For the sake of simplicity, we shall assume that every experiment just deals with a single input/output combination. That is, the finest partitions are reached already after the first symbol. This does not impose any restriction on the partition logic, since given any particular automaton, it is always possible to construct another automaton with exactly the same partition logic as the first one with the above property.

More explicitly, given any partition logic, it is always possible to construct a corresponding automaton with the following specification: associate with every element of the set of partitions a single input symbol. Then take the partition with the highest number of elements and associate a single output symbol with any element of this partition. (There are then sufficient output symbols available for the other partitions as well.) Different partitions require different input symbols; one input symbol per partition. The output function can then be defined by associating a single output symbol per element of the partition (associated with a particular input symbol). Finally, choose a transition function which completely looses the state information after only one transition; i.e., a transition function which maps all automaton state into a single one.

2  Proof of logical equivalence

From the definitions and constructions mentioned in the previous sections it is intuitively clear that, with respect to the empirical logics, generalized urn models and finite automata models are equivalent. Every logic associated with a generalized urn model can be interpreted as an automaton partition logic associated with some (Mealy) automaton (actually an infinity thereof). Conversely, any logic associated with some (Mealy) automaton can be interpreted as a logic associated with some generalized urn model (an infinity thereof). We shall proof these claims by explicit construction. Essentially, the lookup function L and the output function l will be identified. Again, the restriction to Mealy automata is for convenience only. The considerations are robust with respect to variations of finite input/output automata.

2.1  Direct construction of AM from GUM

In order to define an APL associated with a Mealy automaton A=áS,I,O,d,lñ from a GUM U=áU,C,L,L ñ, let u Î U, c Î C, v Î L, and s,s¢ Î S, i Î I, o Î O, and assume |U| = |S|, |C| = |I|, |L| = |O|. The following identifications can be made with the help of the bijections t_S,t_I and t_O:

tS(u)=s,    tI(c)=i,    tO(v)=o, d(s,i) = si     for   fixed  si Î S   and   arbitrary  s Î S,  i Î I, l(s,i) = tO(L (tS-1(s),tI-1(i))).

(1)

More generally, one could use equivalence classes instead of a bijection. Since the input-output behavior is equivalent and the automaton transition function is trivially |L|-to-one, both entities yield the same propositional calculus.

2.2  Direct construction of GUM from AM

Conversely, consider an arbitrary Mealy automaton A=áS,I,O,d,lñ and its associated propositional calculus APL.

Just as before, associate with every single automaton state s Î S a ball type u, associate with every input symbol i Î I a unique color c, and associate with every output symbol o Î O a unique symbol v; i.e., again |U| = |S|, |C| = |I|, |L| = |O|. The following identifications can be made with the help of the bijections t_U,t_C and t_L:

tU(s)=u,   tC(i)=c,   tL(o)=v,   L (u,c) = tL (l(tU-1(u),tC-1(c))). (2)

A direct comparison of (1) and (2) yields

tU-1=tS,   tC-1=tI,   tL-1=tO. (3)

2.3  Schemes using dispersion-free states

Another equivalence scheme uses the fact that both automaton partition logics and the logic of generalized urn models have a separating (indeed, full) set of dispersion-free states. (In what follows, the terms ``dispersion-free state'' ``two-valued state'' ``valuation'' ``dispersion-free probability measure'' are synonyms for measures which take on only the values zero and one. We thereby explicitly exclude dispersion-free measures which take on other values, such as 1/2 and 0, as introduced by Wright [1].) Stated differently, given a finite atomic logic with a separating set of states, then the enumeration of the complete set of dispersion-free states enables the explicit construction of generalized urn models and automaton logics whose logic corresponds to the original one.

This can be achieved by ``inverting'' the set of two-valued states as follows. (The method is probably best understood by considering the examples below.) Let us start with an atomic logic with a separating set of states.

(i) In the first step, every atom of this lattice is labeled by some natural number, starting from ``1'' to ``n'', where n stands for the number of lattice atoms. The set of atoms is denoted by A={1,2,¼, n}.
(ii) Then, all two-valued states of this lattice are labeled consecutively by natural numbers, starting from ``m<sub>1</sub>'' to ``m_r'', where r stands for the number of two-valued states. The set of states is denoted by M={m₁,m₂,¼, m_r}.
(iii) Now partitions are defined as follows. For every atom, a set is created whose members are the numbers or ``labels'' of the two-valued states which are ``true'' or take on the value ``1'' on this atom. More precisely, the elements p_i(a) of the partition P_j corresponding to some atom a Î A are defined by


pi (a) = {k | mk(a)=1,   k Î M}.

The partitions are obtained by taking the unions of all p_i which belong to the same subalgebra P_j. That the corresponding sets are indeed partitions follows from the properties of two-valued states: two-valued states (are ``true'' or) take on the value ``1'' on just one atom per subalgebra and (``false'' or) take on the value ``0'' on all other atoms of this subalgebra.
(iv) Let there be t partitions labeled by ``1'' through ``t''. The partition logic is obtained by a pasting of all partitions P_j, 1 £ j £ t.
(v) In the following step, a corresponding GUM or automaton model is obtained from the partition logic just constructed.

(a) A GUM is obtained by the following identifications (see also [1,p. 271]).

$\bullet$ Take as many ball types as there are two-valued states; i.e., r types of balls.
$\bullet$ Take as many colors as there are subalgebras or partitions; i.e., t colors.
$\bullet$ Take as many symbols as there are elements in the partition(s) with the maximal number of elements; i.e., max_{1 £ j £ t}|P_j| £ n. To make the construction easier, we may just take as many symbols as there are atoms; i.e., n symbols. (In most cases, much less symbols will suffice). Label the symbols by v_l. Finally, take r ``generic'' balls with black background. Now associate with every measure a different ball type. (There are r two-valued states, so there will be r ball types.)
$\bullet$ The ith ball type is painted by colored symbols as follows: Find the atoms for which the ith two-valued state m_i is 1. Then paint the symbol corresponding to every such lattice atom on the ball, thereby choosing the color associated with the subalgebra or partition the atom belongs to. If the atom belongs to more than one subalgebra, then paint the same symbol in as many colors as there are partitions or subalgebras the atom belongs to (one symbol per subalgebra).
This completes the construction.
(b) A Mealy automaton is obtained by the following identifications (see also [3,pp. 154-155]).

$\bullet$ Take as many automaton states as there are two-valued states; i.e., r automaton states.
$\bullet$ Take as many input symbols as there are subalgebras or partitions; i.e., t symbols.
$\bullet$ Take as many output symbols as there are elements in the partition(s) with the maximal number of elements (plus one additional auxiliary output symbol ``*'', see below); i.e., max_{1 £ j £ t}|P_j| £ n+1.
$\bullet$ The output function is chosen to match the elements of the state partition corresponding to some input symbol. Alternatively, let the lattice atom a_q Î A must be an atom of the subalgebra corresponding to the input i_l. Then one may choose an output function such as


l(mk,il) = ì ï í ï î aq    if   mk (aq) = 1 *      if   mk (aq) = 0

with 1 £ k £ r and 1 £ l £ t. Here, the additional output symbol ``*'' is needed.
$\bullet$ The transition function is r-to-1 (e.g., by d(s,i)=s₁, s,s₁ Î S, i Î I), i.e., after one input the information about the initial state is completely lost.
This completes the construction.

2.4  Example 1: The generalized urn logic L₁₂

In what follows we shall illustrate the above constructions with a couple of examples. First, consider the generalized urn model

á{u1,¼,u5},{red,green},{1,¼,5},L ñ

with L listed in Table 1(a).

The associated Mealy automaton can be directly constructed as follows. Take t_S=t_O = id, where id represents the identity function, and take t_I(red)=0 and t_I(green)=1, respectively. Furthermore, fix a (five×two)-to-one transition function by d(.,.)=1. The transition and output tables are listed in Table 1(b). Both empirical structures yield the same propositional logic L₁₂.

2.5  Example 2: The automaton partition logic L₁₂

Now define the following GUM as follows. There are two subalgebras with the atoms 1,2,5 and 3,4,5, respectively. Since there are five two-valued measures corresponding to five ball types. They are colored according to the coloring rules defined above. and L as listed in Table 2.

2.6  Example 3: GUM of the Kochen-Specker ``bug'' logic

There are 14 dispersion-free states which are listed in Table 3(a). The associated GUM is listed in Table 3(b).

3  Discussion

GUMs and automata are capable to serve as models for particular types of lattices with a sufficient number of two-valued states (e.g., with a separating set of states). Yet it is this very property which makes impossible the realization of other, more exotic states, which have no classical and not even a quantum mechanical counterpart. Take, as an example, the Wright state [1,7] on the pentagon (or any n-agon, with odd n > 3, n=2k+1, k=2,3,¼) Greechie diagram with value 1/2 on the five vertices and 0 on each middle atom (three atoms per subalgebra). The 11 two-valued measures suffice to generate GUMs and finite automata with that logical structure, but none such model realizes the Wright state.

Acknowledgments

References

[1]

Ron Wright. The state of the pentagon. A nonclassical example. In A. R. Marlow, editor, Mathematical Foundations of Quantum Theory, pages 255-274. Academic Press, New York, 1978.

[2]

Ron Wright. Generalized urn models. Foundations of Physics, 20:881-903, 1990.

[3]

Karl Svozil. Randomness & Undecidability in Physics. World Scientific, Singapore, 1993.

[4]

Martin Schaller and Karl Svozil. Automaton logic. International Journal of Theoretical Physics, 35(5):911-940, May 1996.

[5]

Anatolij Dvurecenskij, Sylvia Pulmannová, and Karl Svozil. Partition logics, orthoalgebras and automata. Helvetica Physica Acta, 68:407-428, 1995.

[6]

Cristian Calude, Elena Calude, Karl Svozil, and Sheng Yu. Physical versus computational complementarity I. International Journal of Theoretical Physics, 36(7):1495-1523, 1997.

[7]

Karl Svozil. Quantum Logic. Springer, Singapore, 1998.

[8]

Simon Kochen and Ernst P. Specker. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics, 17(1):59-87, 1967. Reprinted in [10,pp. 235-263].

[9]

Ernst Specker. private communication, 1999.

[10]

Ernst Specker. Selecta. Birkhäuser Verlag, Basel, 1990.