The aim of this paper is to present to philosophers of physics some results in the theory of automata, especially the theory concerned with determining the initial state of the automaton: results which are analogons to the phenomena of ``complementarity'' or ``non-Booleanness'' which occur in quantum mechanics.
It has long been known that any finite input/output system can be modelled by finite automata [Paz(1971)]. The study of finite automata was motivated from the very beginning by their analogy to quantum systems [Moore(1956),Foulis and Randall(1972),Randall and Foulis(1973)]. Finite automata are universal with respect to the class of computable functions in the (usual) sense that universal networks of automata can compute any effectively (Turing-) computable function. Conversely, any feature emerging from finite automata is reflected by any other universal computational device. Their non-Boolean intrinsic propositional calculus closely resembles finite quantum mechanical systems [Svozil(1993),Schaller and Svozil(1994),Schaller and Svozil(1995),Schaller and Svozil(1996),Dvure censkij et al.(1995)].
The considerations to follow in this article are not technically complicated. Nevertheless, the corresponding ideas turn out to be highly nontrivial and nonclassical, sometimes mindboggling [Greenberger et al.(1993)].
A finite deterministic sequential machine or automaton [Moore(1956),Hopcroft and Ullman(1979),Hartmanis and Stearns(1966)] is a device with a finite set of inputs which can be applied in a sequence, with a finite set of internal configurations or states, and with a finite set of outputs. Furthermore the present internal configuration and input uniquely determine the next internal configuration and the output.
A Mealy automaton is a quintuple
M = (S,I,O,d,l), where
I is a finite (nonempty) set of inputs;
O is a finite (nonempty) set of outputs;
d: S×I® S is a computable transition function;
l: S×I® O is a computable output function.
A state machine is a triplet of M = (S,I,d) with no outputs and no output function.
A combinatorial circuit or gate is a triplet of M = (I,O,l), which maps inputs into outputs, regardless of past history. It can also be modelled as a one state Mealy automaton.
In what follows and if not mentioned otherwise, s,i,o stand for a particular internal state, input and output, respectively.
Mealy machines are represented by flow tables and state graphs. To illustrate this, consider a Mealy machine Me = (S,I,O,d,l) which has n states, n inputs and 2 outputs. That is
| |||||||||||||||||||
| |||||||||||||||||||||||||
| s\c | d | l | ||||||
| 1 | 2 | ¼ | n | 1 | 2 | ¼ | n | |
| 1 | 1 | 2 | ¼ | n | 1 | 0 | ¼ | 0 |
| 2 | 1 | 2 | ¼ | n | 0 | 1 | ¼ | 0 |
| : | 1 | 2 | ¼ | n | 0 | 0 | ¼ | 0 |
| n | 1 | 2 | ¼ | n | 0 | 0 | ¼ | 1 |
1.00mm
Picture Omitted
Two automata M1 = (S1,I1,O1,d1,l1) and M2 = (S2,I2,O2,d2,l2) of the same type are isomorphic if and only if there exist three one-to-one mappings f:S1® S2, g:I1® I2, h:O1® O2 such that f[d1(s1,i1)] = d2 [f(s1),g(i1)] and h[l1(s1,i1)] = l2 [f(s1),g(i1)], where sj Î Sj and ij Î Ij, j Î {1,2}. The triple (f,g,h) is an isomorphism between M1 and M2. An isomorphism just renames the states, the inputs and the outputs. From a purely input/output point of view, g as well as h (or h-1) are combinatory circuits and M1 performs similarly to the serial connection (see below) h-1M2 g of the machines g, M2 and h-1.
The serial connection of the two machines M1 = (S1,I1,O1,d1,l1) and M2 = (S2,I2,O2,d2,l2) for which O1 = I2 is the machine [Hartmanis and Stearns(1966)]
|
d[(s1,s2),i] = ( d1(s1,i),d2[s2,l(s1,i)]) and l[(s1,s2),i] = l2[s2,l1(s1,i)].
The parallel connection of the two machines M1 = (S1,I1,O1,d1,l1) and M2 = (S2,I2,O2,d2,l2) is the machine [Hartmanis and Stearns(1966)]
|
By suitable serial and parallel connections it is possible to construct networks of automata or combinatorial circuits (gates) which are universal relative to the class of Turing-computable algorithms. That is, all algorithms computable on a Turing machine are computable by serial and parallel connections of finite automata and vice versa.
Suppose that the only unknown feature of an automaton is its initial state; all else is known. The automaton is presented in a black box, with input and output interfaces. The task in this complementarity game is to find (partial) information about the initial state of the automaton [Moore(1956)]. This is sometimes referred to as the state identification problem [Conway(1971),Brauer(1984)].
To illustrate this, consider the Mealy automaton Me discussed above. Input/output experiments can be performed by inputting of one symbol i (in this example, more inputs yield no finer partitions). Let us assume that one inputs i = 5. This experiment is able to distinguish between state s = 5 and all the other states; hence it induces a partition (suppose n > 5)
|
The automaton propositional calculus and the associated partition logic is the set of all partitions
|
|
Let E be an experiment (a preset or adaptive one), and let lE(s) denote the output obtained when one performs E on an initial state s. lE defines a mapping of S to the set of output sequences O*. We define an equivalence relation on the state set S by
|
There is also another way to construct the experimentally decidable propositions of an experiment E. Let lE(P) = Ès Î PlE(s) be the direct image of P under lE for any P Í S. We denote the direct image of S by OE; i.e., OE = lE(S).
It follows that the most general form of a prediction concerning the outcome W of the experiment E is that W lies in a subset of OE. Therefore, the experimentally decidable propositions consist of all inverse images lE-1(Q) of subsets Q of OE, a procedure which can be constructively formulated (e.g., as an effectively computable algorithm), and which also leads to the Boolean algebra BE.
Let \frak B be the set of all Boolean algebras BE. We call the partition logic R = (S,\frak B) an automaton propositional calculus. That is, we paste all Boolean subalgebras together. For instance, in the particular example discussed above, the Boolean subalgebras are v(1),v(2),¼,v(n).
If one does not know the automaton's initial state, one has to choose which experiment to perform. Computational complementarity manifests itself in the following way. Let us assume that no experiment gives a definite answer to the initial-state identification problem. (The classical ``initial value problem'' has a very different meaning in physics.) Suppose further that the actual performance of any one experiment makes impossible all the other experimental measurements-this can, for instance be achieved by irreversible transition and output functions (d and/or l are many-to-one). Then the first (and only) experiment decides which one of the possible observables is actually being measured. ``Observable'' here means a statement such as ``the automaton is in state m or in state n.'' After this measurement, the other remaining observables cannot be measured any more. We shall refer to such a class of observables as complementary ones.
Quantum logic, as pioneered by Birkhoff and von Neumann [Birkhoff and von Neumann(1936)], is usually derived from Hilbert space. There, the logical primitives, such as propositions and the logical operators ``and'', ``or'' and ``not'' are defined by Hilbert space entities. For instance, consider the threedimensional, real Hilbert space \Bbb R3 with the usual scalar product (v,w): = åi = 13viwi, v,w Î \Bbb R3. Any proposition is identified with a closed linear subspace of \Bbb R3. For instance, the zero vector corresponds to a false statement. Any line spanned by a nonzero vector corresponds to the statement that the physical system has an observable property associated with the projection operator corresponding to the ondimensional subspace spanned by the vector. Any plane formed by linear combinations of two (non-collinear) vectors v,w corresponds to the statement that the physical system has either the property corresponding to v or the property corresponding to w. The whole Hilbert space \Bbb R3 corresponds to the tautology (true propositions). The logical ``and''-operation is identified with the set theoretical intersection of two propositions; e.g., with the intersection of two planes. The logical ``not''-operation, or the ``complement'', is identified with taking the orthogonal subspace; e.g., the complement of a line is the planes orthogonal to that line.
In this top-down approach, one arrives at a propositional calculus which resembles the classical one, but differs from it in several important aspects. They are non-Boolean, i.e., non-distributive, algebraic structures.
Furthermore, as was first pointed out by Kochen and Specker in the context of partial algebras [Kochen and Specker(1967),Zierler and Schlessinger(1965),Redhead(1990),Mermin(1993)], there exist certain finite sets of lines, such that the partial Boolean algebra generated by this set does not admit of any monomorphism into the two-element Boolean algebra.
It has been demonstrated recently [Svozil and Tkadlec(1996)] that no Kochen-Specker-type constructions are possible in automaton partition logic. This can be understood intuitively as arising from the definiteness and context-independence of any proposition regarding an automaton state: automaton partition logic is nonclassical (e.g., nondistributive) but context-independent. The context-dependence associated with the Kochen-Specker construction is deeply rooted in the infinite propositional structure of quantum logic derived from Hilbert space. Although the explicit construction operates with a finite number of rays (corresponding to elementary true-false propositions), it generates an infinite number of such propositions [Havlicek and Svozil(1996)].
Let (\frak L, Ú,Ù, ¢,0,1) be an algebraic structure. Thereby, \frak L is a non-empty set of elements to be interpreted as propositions which are, at least in principle, operational. Ú,Ù are binary operations interpretable as ``or'' and ``and,'' respectively. ¢ is a unary operation interpretable as ``not.'' 0,1 are elements of \frak L interpretes as the proposition which is always false and always true (tautology), respectively.
A partially ordered set (poset) is a system \frak L in which a binary order relation £ (inverse ³ ) is defined, which satisfies (i) a £ a, for all a Î \frak L (reflexivity); (ii) a £ b and b £ cÞ a £ c (transitivity); (iii) a £ b and b £ aÞ a = b (antisymmetry).
A partially ordered system \frak L with order relation £ (inverse ³ ) is a lattice if and only if any pair a,b of its elements has (i) a greatest lower bound aÙb and (ii) a least upper bound aÚb.
a¢ is called the orthocomplement (orthogonal complement) of a, if
aÚa¢ = 1, aÙa¢ = 0, (a¢)¢ = a and if a £ bÞ a¢ ³ b¢. The structure (\frak L, Ú,Ù, ¢,0,1) is called the ortholattice.
A Boolean algebra is an ortholattice which satisfies the distributive laws a Ú(bÙc) = (aÚb)Ù(aÚc) and a Ù(bÚc) = (aÙb)Ú(aÙc). A Boolean algebra with n atoms is denoted by 2n. An atom a of a lattice \frak L covers the least element
0; i.e., 0 £ a and that 0 £ x £ a implies x = a.
The structure is modular if the modular law (aÚb)Ùc = aÚ(b Ùc) is satisfied for all a £ c. The structure is orthomodular if the orthomodular law a £ b Þ b = aÚ(bÙa¢) is satisfied.
Besides automaton logics, there are other ``quasi-classical'' examples of non-Boolean algebras, such as Wright's generalized urn models [Wright(1990),Wright(1978)] and Aerts' models [Aerts(1995)]. Another interesting example is Cohen's ``firefly in a box'' scenario [Cohen(1989)] with a three-chamber box [Dvure censkij et al.(1995)] as depicted in Fig. 3.
The firefly flies around the three chambers. Furthermore, it is free to light up or not to light up. The sides of the box are windows with vertical lines down their centers. Consider the three experiments, corresponding to the three windows A, B and C. For each experiment E, one records lE, rE, nE if one sees a light to the left (lE) or to the right (rE) of the center line or if one sees no light at all (ne). One can identify rA = lC = : e, rC = lB = : c, rB = lA = : a (but one should not identify f: = nA, b : = nB, d: = nC). The propositional logic of this model is represented by the Hasse diagram drawn in Fig. 4.
The following miniatlas contains a sample collection of Hasse diagrams. It is by no means intended as a complete collection of Hasse diagram features.
One difference between automaton logic and quantum logic should be kept in mind. The Hasse diagrams originating from finite automata are finite almost by definition. The Hasse diagrams originating from Hilbert-space quantum mechanics [Birkhoff and von Neumann(1936)] are continuously (À1) infinite. Furthermore, any finite quantum propositional structure which does not allow a two-valued measure (classically interpretable as the logical values ``true'' and ``false'') and therefore implements a Kochen-Specker type contradiction is embedded into an countably infinite (À0) propositional structure [Svozil and Tkadlec(1996),Havlicek and Svozil(1996)]. Therefore, it will never be possible to completely reduce quantum logic to automaton logic.
Nevertheless, finite structures are worth studying. They can serve as models for complementarity. They show non-classical features not observed in quantum physics. For instance, the propositional structure needs not be a partially ordered set (cf. section 3.1.5). It could be transitive and Boolean, but in a peculiar way feature complementary (cf. section 3.1.6).
It can be shown by a straightforward construction [Svozil(1993)] that every partition logic corresponds to an automaton logic.
0.80mm
Picture Omitted
n Î \Bbb R becomes a continuous variable.]
| |||||||||||||||||||||||||||||
This lattice MOn occurs in quantum mechanics (logic) if one considers the measurement of the spin component of an electron in n directions. So, in a finitistic sense, the ``Mealy electron'' Me defined in Fig. 1 faithfully represents the spin observables of an electron. But quantum mechanics supposes that the spin component of an electron can be measured along an arbitrary, continuous direction. In this sense, already two-dimensional Hilbert space implies that a complete representation of a quantum object such as spin cannot be given by finitistic entities.
0.80mm
Picture Omitted
\frak L1n > 2 is not a subortholattice of threedimensional Hilbert space \frak H3 [Svozil and Tkadlec(1996)]. It is a nontrivial pasting. It is not a horizontal sum as the logics before.
| |||||||||||||||||||||||||||||
One (but not the only one) particular way to construct a corresponding automaton logic would be to define a Mealy automaton with as many input symbols as there are elements of P. The number of output symbols should be three. The transition function could be trivial; i.e., d(s) = 1 for all sin S. The output function should reflect the partitions; e.g., l(1,1) = 1, l(2,1) = 2,
l(2,1) = ¼ = l(2,1) = 3.
1.00mm
Picture Omitted
| ||||||||||||||
(1Ú2) and another one deciding the ``implication'' (1Ú2) ``®'' (1Ú2Ú3), but none deciding the ``implication'' 1 ``®'' (1Ú2Ú3). The reason for this is that the last ``relation'' is not experimentally testable.
0.85mm
Picture Omitted
| ||||||||||||||||||||||||||||||||||
The resulting propositional calculus is Boolean, but has a non-classical feature of complementarity insofar as there exists no experiment deciding between any one of the different initial states. As in the last example, the reason for this feature is that certain ``relations'' are not experimentally testable. That is, there is simply no experiment which could be made to verify, for instance, 1 ``®'' {1,2,3}, although the statements 1 ``®'' {1,3} and {1,3} ``®'' {1,2,3} are testable singularly.
1.00mm
Picture Omitted
0.80mm
Picture Omitted
{11} = {a1,b1} and {12} = {a2,b2} do not belong to the diagram, because-as they do not include propositions about the second or first automaton factor-they cannot be realized in any experiment.
| ||||||||||||||||||||||||
One automaton realization is the Mealy automaton M, which can be parallel decomposed into two Mealy automata M1, M2 such that M = M1 || M2 according to
M =
| s/i | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 1 | 1 | 1 | 1 |
| 2 | 1 | 2 | 3 | 4 | 2 | 2 | 2 | 1 |
| 3 | 1 | 2 | 3 | 4 | 3 | 3 | 1 | 2 |
| 4 | 1 | 2 | 3 | 4 | 3 | 2 | 3 | 3 |
| s/i | a | b | a | b |
| A | A | B | 0 | 0 |
| B | A | B | 1 | 1 |
| s/i | i | ii | i | ii |
| I | I | II | 0 | 0 |
| II | I | II | 1 | 1 |
The proper identifications relating the states of M,M1,M2 are A º {1,2}, B º {3,4}, I º {1,3}, II º {2,4} and 1 º A·I, 2 º A·II, 3 º B·I, 4 º B·II. Here, the ``·''-product of two sets of states is their set theoretic intersection [Hartmanis and Stearns(1966)]. The proper identifications relating the input symbols of M1,M2,M are ai º 1, aii º 2, bi º 3, bii º 4.
Note that the output table of M reproduces the partition logic P. The i'th input generates the i'th partition by associating the output symbol j to the j'th element of the i'th partition.
1.00mm
Picture Omitted
Let a1 º 1, a2 º 2, a3 º 3, b1 º 4, b2 º 5, b3 º 6. A partition logic isomorphic 22Ä22Ä22 is
| ||||||||||||||||||||||||||||||||||||||||||||
One automaton realization is the Mealy automaton M, which can be parallel decomposed into two Mealy automata M1, M2 such that M = M1 || M2 || M3 according to
M =
| s/i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 2 | 4 | 2 | 4 | 2 | 1 | 2 | 1 |
| 3 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | 3 | 4 | 4 | 3 | 2 | 1 | 1 |
| 4 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 4 | 4 | 4 | 4 | 4 | 3 | 3 | 2 |
| 5 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 4 | 2 | 4 | 2 | 1 | 4 | 1 | 3 |
| 6 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 4 | 4 | 3 | 3 | 1 | 1 | 4 | 4 |
| s/i | a | b | a | b |
| A | A | B | 0 | 0 |
| B | A | B | 1 | 1 |
| s/i | i | ii | i | ii |
| I | I | II | 0 | 0 |
| II | I | II | 1 | 1 |
| s/i | g | d | g | d |
| G | G | D | 0 | 0 |
| D | G | D | 1 | 1 |
The proper identifications relating the states of M,M1,M2 are A º {1,2,3}, B º {4,5,6}, I º {1,5,6}, II º {2,3,4}, G º {1,3,5}, D º {2,4,6}, and 1 º A·I·G, 2 º A·II·D, 3 º A·II·G, 4 º B·II·D, 5 º B·I·G, 6 º B·I·D. Note again that the output table of M reproduces the partition logic P.
I have attempted to enumerate some rationally conceivable forms of complementarity, or, more specifically, of the logico-algebraic structure of propositions about observable phenomena. This is in the spirit of Foulis and Randall [Foulis and Randall(1972),Randall and Foulis(1973)], but with a definite algorithmic flavour. Thereby, structures in algorithmics have been related to and compared with logical and physical forms. A small collection of low-complexity structures has been discussed. These examples mainly originate from quantum systems and automata theory, including the serial and parallel composition of deterministic Moore and Mealy automata.
It should be emphasized that complementarity is not directly related to diagonalization [Gödel(1931),Turing(1937),Rogers, Jr.(1967),Odifreddi(1989)]; it is, rather, a second, independent source of undecidability. It is already realizable at an elementary `pre-diagonalization' level, i.e., without the requirement of computational universality or its arithmetic equivalent. The corresponding machine model is the class of finite automata.
Since any finite state automaton can be simulated by a universal computer, complementarity is a feature of sufficiently complex deterministic universes as well. To put it pointedly: if the physical universe is conceived as the product of a universal computation, then complementarity is an inevitable feature of the perception of observers.