\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage{graphicx}
\usepackage{amsfonts}
%\documentstyle[amsfonts]{article}
\RequirePackage{times}
%{\Bbb R}equirePackage{courier}
\RequirePackage{mathptm}
\begin{document}
 \title{Extrinsic-intrinsic concept \& complementarity}
\author{K. Svozil\\
 {\small Institut f\"ur Theoretische Physik}  \\
  {\small Technische Universit\"at Wien   }     \\
  {\small Wiedner Hauptstra\ss e 8-10/136}    \\
  {\small A-1040 Vienna, Austria   }            \\
  {\small svozil@tuwien.ac.at}}
\date{}
\maketitle

\section{Introduction}
 Epistemological, the
 {\em intrinsic/extrinsic}
 concept, or, by another naming \cite{roessler-87,roessler-92}, the
{\em endo\-phy\-sics/exophysics}
 concept, is related to the question of how
 a mathematical or a logical or an algorithmic  universe
 is perceived   from within/from the outside.
 The physical universe, by definition, can be perceived
 from within only.

 {\em Extrinsic} or {\em exophysical}
 perception can be conceived as a hierarchical process, in which the
 system under observation and the experimenter form a two-level
 hierarchy. The system is laid out  and the experimenter peeps at
 every relevant feature of it without changing it.
 The restricted entanglement between the system and the experimenter
 can be represented by a one-way
 information flow from the system to the experimenter; the system is
 not affected by the experimenter's actions.
 (Logicians might prefer the term {\em meta} over {\em exo}.)


 {\em Intrinsic} or {\em endophysical} perception can be conceived
 as a non-hierarchical effort. The
 experimenter is part of the universe under observation.
 Experiments
 use devices and procedures
 which are realisable by internal resources, i.e., from within the
 universe.
 The total integration of the experimenter in the observed system can
 be represented
 by a  two-way information flow, where ``measurement apparatus'' and
 ``observed entity'' are
 interchangeable and any distinction between them
 is merely a matter of intent and
 convention.
 Endophysics
 is limited by the self-referential character of any measurement.
 An intrinsic measurement can often be related to the paradoxical
 attempt to obtain the
 ``true'' value of an observable while --- through interaction --- it
 causes ``disturbances'' of the entity to be measured, thereby changing
 its state.
 Among other questions one may ask,
{\em  ``what
 kind of experiments are intrinsically operational and what type of
 theories will be intrinsically reasonable?''}

 Imagine, for example,  some artificial intelligence living in a
 (hermetic) cyberspace.
 This agent
 might develop a ``natural science''
 by performing experiments and developing
 theories.
 It is tempting to speculate that also a figure in a novel,
 imagined by the poet and the reader, is such an agent.

  Since in cyberspace only {\em
 syntactic} structures are relevant, one might wonder if concerns of
 this agent about its ``hardware basis,'' e.g., whether it
 is ``made of'' billard balls, electric circuits, mechanical relays
 or nerve cells,
 are mystic or even possible (cf. H. Putnam's
brain-\-in-\-a-\-tank analysis \cite{putnam:81}).
 I dont think this is necessarily so, in particular if the agent could
 influence some features of this hardware basis.
One example is a hardware damage caused by certain computer viruses
by ``heating up'' computer components such as
storage or processors.
I would like to call this type of ``back-reaction'' of a virtual reality
on its computing agent {\em ``virtual backflow interception''} (VBI).
Intrinsic
phenomenologically, VBI could manifest itself by some violation of a
``superselection rule;'' i.e., by some virtual phenomenon which violates
the fundamental laws of a virtual reality, such as symmetry \&
conservation principles.



 No attempt is made here to (re-)write
 a comprehensive history of related concepts;
 but
 a few hallmarks are mentioned without claim of completeness.
 Historically,
 Archimedes conceived {\em ``points
 outside the world, from which one could move the earth.''}
 Archimedes' use of ``points outside the world'' was in a
 mechanical rather than in a metatheoretical context:
 he claimed to be able to move any given weight by any given
 force, however small.
The 18'th century physicist B. J. Boscovich  realised that
it is not possible to measure motions or transformations if the whole
world, including all measurement apparata and observers therein, becomes
equally affected by these motions or transformations
(cf. O. E. R\"ossler \cite{roessler-92}, p. 143).
 Fiction writers
 informally elaborated consequences of intrinsic perception.
 E. A.
 Abbot's  {\sl Flatland}  describes the life
 of two- and onedimensional creatures and their confrontation with
 higher dimensional phenomena.
 The {\it Freiherr von M\"unchhausen}  rescued himself from a
 swamp by dragging himself out by his own hair.
 Among contemporary science fiction authors, D. F. Galouye's {\sl
 Simulacron Three} and St. Lem's {\sl Non Serviam} study some aspects
 of artificial intelligence in what could be called ``cyberspaces.''
 Media artists such as Peter Weibel create ``virtual realities''  or
``cyberspaces'' and  are particulary concerned about the
{\em interface} between ``reality'' and ``virtual reality,''
both practically and philosophically.
Finally, by outperforming television \& computer
games, commercial
``virtual reality'' products might become very big business.
From these examples it can be seen that concepts related to intrinsic
perception may become fruitful for physics, the computer sciences and
art as well.


 Already in 1950 (19 years after the publication of G\"odel's
 incompleteness theorems),
 K. Popper has questioned the completeness of self-referential
 perception
 of ``mechanic'' computing devices \cite{popper-50}. Popper uses
 techniques similar to
 Zeno's paradox (which he calls  ``paradox of Tristram Shandy'')
 and ``G\"odelian sentences'' to argue for a kind of ``intrinsic
 indeterminism.''

 In a pioneering study on the theory of (finite) automata, E. F. Moore
 has presented {\sl
 Gedanken-experiments on sequential machines} \cite{moore}.
 There, E. F. Moore
 investigated  automata featuring, at least to some extend,
 similarities to the quantum mechanical
 uncertainty principle.
 In the book {\sl Regular Algebra and Finite Machines} \cite{conway},
 J. H. Conway has developed these ideas further from a formal point of
 view without relating them to physical applications.
 Probably the best review of experiments on Moore-type automata can be
 found in W. Brauer's book {\sl Automatentheorie} \cite{brauer-84} (in
 German).

 D. Finkelstein \cite{finkelstein-79,finkelstein-83} has considered
 Moore's findings from a more physical point of view, introducing an
 ``experimental logic of automata'' and  the term
 {\em ``computational complementarity.''}
 An illuminating account on endophysics topics can be
 found in O. E. R\"ossler's article on {\sl Endophysics}
 \cite{roessler-87}, as well as in his book {\sl Endophysics}
(in German)  \cite{roessler-92};
 O. E. R\"ossler is a major driving
force in this area.
 Also H. Primas has considered endophysical and exophysical
 descriptions in various contexts \cite{primas-88}.

 The terms {\em ``intrinsic''} and {\em ``extrinsic''} appear
 in the author's studies on
 intrinsic time scales in arbitrary dispersive media
  \cite{svo-83,svo-86,svo5}. There, the intrinsic-extrinsic concept
 has been re-invented (probably for the 100'th time, and, I solemnly
 swear)
 independently. It is argued  that, depending on dispersion relations,
 creatures in a ``dispersive medium''
 would develop a theory of coordinate transformation very similar to
 relativity theory.
 Another proposal by the author was to consider a new type of
 ``dimensional
 regularisation'' by assuming that the space-time
support of
 (quantum mechanical) fields is a fractal
 \cite{sv4}.
 In this approach one considers a fractal space-time of Hausdorff
 dimension $D=4-\epsilon$, with $\epsilon \ll 1$,
 which is embedded in a space of higher dimension, e.g., ${\Bbb R}^{n\ge 4}$.
 Intrinsically, the (fractal)
 space-time is perceived ``almost'' as the usual fourdimensional
space.

 Besides such considerations, J. A. Wheeler \cite{wheeler}, among
 others, has emphasised
 the role of {\em observer-participancy.} In the context of what is
 considered by the Einstein-Podolsky-Rosen argument \cite{epr} as
 ``incompleteness'' of quantum theory, A. Peres and W. H. Zurek
 \cite{peres,peres-85} and J. Rothstein \cite{rothstein} have attempted
 to relate quantum complementarity to G\"odel-type incompleteness.


 In what follows, the intrinsic-extrinsic concept
 will be made precise in an {\em algorithmic} context, thereby
 closely following
 E. F. Moore
 \cite{moore}.
 The main reason for the algorithmic approach is
 that algorithmic universes (or, equivalently,
 formal systems)
 are the royal road to
 the study of undecidability.
 The intrinsic-extrinsic concept will be applied to investigate
 {\em computational
 complementarity}
and {\em intrinsic indeterminism}
 both in the
 algorithmic context.



 \section{Gedankenexperiments on finite automata}
 In a groundbreaking study \cite{moore},
 Edward Moore analysed two kinds
 of {\it Gedankenexperiments} on finite automata,
 which will be slightly adapted for the present purposes.
 In both
 cases, the automaton is treated as a ``black box'' in the following
 sense:

 {\it (i)} only
 the input and output terminals of the automaton are accessible.
 The experimenter is allowed to perform experiments {\it via} these
interfaces in the form of stimulating the automaton with input
sequences and receiving output sequences from the automaton.
 The experimenter is not permitted to ``open up'' the automaton,
 but

 {\it (ii)} the transition and output table (diagram) of the automaton
 (in its reduced form) is known to the experimenter
 (or, if you prefer, is given to the experimenter by some ``oracle'').

 The most important problem, among others, is the {\em distinguishing
 problem:} it is known that an automaton
 is in one of a particular class of internal states: find that state.


 In the first kind of experimental situation, only a {\em single} copy
 of the automaton is accessible to the experimenter. The second type of
 experiment operates with an {\em arbitrary number} of automaton
 copies. Both cases will be discussed in detail below.

 If the input is some {\em predetermined} sequence, one may call
 the experiment a {\em preset experiment}. If, on the other hand, (part
 of) the
 input sequence depends on (part of) the output sequence, i.e., if the
 input is {\em adapted} to the reaction of the automaton, one may call
 the experiment an {\em adaptive experiment.}
We shall be mostly concerned with preset experiments, yet adaptive
experiments can be used to solve certain problems with automaton
propositional calculi.

 Research along these lines has been pursued by S. Ginsburg
 \cite{ginsburg-58},  A. Gill \cite{gill-61},
 J. H. Conway \cite{conway} and
 W. Brauer \cite{brauer-84}.



 \subsection{Single-automaton configuration}

 In the first kind of Gedankenexperiment,
 only {\em one single}
 automaton copy is presented to the experimenter.
 The problem is to determine the initial state of the
 automaton, provided its transition and output
 functions are known (distinguishing problem).
 In a typical experiment, the  automaton
 is ``feeded'' with a sequence of input symbols
 and responds by a sequence of output symbols.
 An input-output analysis then reveals information about the
 automaton's original state.

 Assume for the moment that such an
 experiment  induces a state
 transition of the automaton. I.e., after the experiment, the
 automaton is not in the
 original initial state. In this process a loss of potential
 information about the automaton's initial state may occur.
 In other words:
 certain measurements, while measuring
 some particular feature of the automaton, may make impossible the
 measurement of other features of the automaton.
 This irreversible change of the automaton state  is one aspect
 of the ``observer-participancy'' in the single-automaton
 configuration.
 (This is not the case for the multi-automaton situation discussed
 below, since the availability of an arbitrary number of automata
 ensures the possibility of an arbitrary number of
 measuring processes.)



 In developing the intrinsic concept further,
 the automaton and the experimenter are ``placed'' into  a {\em
 single} ``meta''-automaton.
 If the experimenter reacts
 mechanically, this can be readily achieved by simulating both
 the original finite deterministic ``black box'' automaton as well as
 the experimenter and their interplay by a universal automaton.
 One can imagine such a situation as one subprogram
 checking another subprogram, also including itself.
   For an illustration, see Fig. \ref{f-s-experiment}.
\begin{figure}
\begin{center}
\unitlength=0.70mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(150.00,71.00)
\put(21.00,46.00){\framebox(121.00,16.00)[cc]{experimenter}}
\put(21.00,11.00){\framebox(121.00,15.00)[cc]{automaton}}
\put(35.00,46.00){\vector(0,-1){19.00}}
\put(122.00,26.67){\vector(0,1){18.00}}
\put(39.00,36.00){\makebox(0,0)[lc]{input}}
\put(102.00,35.00){\makebox(0,0)[lc]{output}}
\put(15.00,7.00){\framebox(135.00,64.00)[cc]{}}
\put(95.00,65.00){\makebox(0,0)[lb]{``meta''-automaton}}
\end{picture}
\end{center}
\caption{Schematic diagram of an experiment on a single automaton,
 both taking place in a ``meta''-automaton.
 \label{f-s-experiment}}
\end{figure}

In certain cases it is necessary to iterate this picture in the
following way. Suppose, for instance, the experimenter attempts a {\em
complete} intrinsic description. Then, the experimenter has to give a
complete description of his own intrinsic situation.
In order to be able
to
model the own intrinsic viewpoint, the experimenter has to introduce an
or system
 which is a {\it replica} of its own universe.
This amounts to substituting the ``meta''-automaton for the
automaton in Fig. \ref{f-s-experiment}.
Compare also a drawing by O. E. R\"ossler \cite{roessler-922},
 Fig. \ref{l:rossl},
where
``$\approx $''
stands for the interface, which is denoted by the symbols
``$\leftrightarrow $'' throughout this article.
\begin{figure}
\begin{center}
$\;$
%  \epsfysize=4 true cm
\includegraphics[width=90mm]{ch-roess.ps}
% {\Huge ch-roessl.ps}   \epsffile{ch-roessl.ps}
\end{center}
\caption{ Author's notes from a seminar talk by O. E. R\"ossler.
 \label{l:rossl}}
\end{figure}
Yet, in order to be able
to
model intrinsic viewpoint of a new experimenter in this new universe,
this new experimenter has to introduce another system
 which is a {\it replica} of its own universe, $\ldots$,
resulting in an iteration {\it ad infinitum.}
One may conjecture that an observer in a hypothetical universe
corresponding to the
``fixed point'' or ``invariant set'' of this process has complete
self-comprehension; see Fig. \ref{l.fiss}.
\begin{figure}
\begin{center}
\unitlength=0.80mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(140.00,100.00)
\put(10.00,10.00){\framebox(130.00,90.00)[cc]{}}
\put(17.00,17.00){\framebox(80.00,50.00)[cc]{}}
\put(23.00,23.00){\framebox(40.00,20.00)[cc]{}}
\put(27.00,27.00){\framebox(17.00,8.00)[cc]{}}
\put(29.00,29.00){\framebox(7.00,3.00)[cc]{}}
\put(30.00,30.00){\framebox(3.00,1.00)[cc]{}}
\put(30.00,30.00){\rule{2.00\unitlength}{1.00\unitlength}}
\put(115.00,17.00){\framebox(21.00,76.00)[cc]{{\Large exp.}}}
\put(78.00,23.00){\framebox(16.00,39.00)[cc]{exp.}}
\put(52.00,27.00){\framebox(9.00,12.00)[cc]{{\small exp.}}}
\put(39.00,29.00){\framebox(3.00,4.00)[cc]{{\tiny exp.}}}
\put(34.00,30.00){\framebox(1.00,1.00)[cc]{}}
\put(34.00,31.00){\vector(-1,0){1.00}}
\put(33.00,30.00){\vector(1,0){1.00}}
\put(36.00,29.00){\vector(1,0){3.00}}
\put(39.00,31.00){\vector(-1,0){3.00}}
\put(44.00,28.00){\vector(1,0){8.00}}
\put(52.00,34.00){\vector(-1,0){8.00}}
\put(63.00,29.00){\vector(1,0){15.00}}
\put(78.00,41.00){\vector(-1,0){15.00}}
\put(97.00,20.00){\vector(1,0){18.00}}
\put(115.00,64.00){\vector(-1,0){18.00}}
\put(42.00,84.00){\makebox(0,0)[cc]{{\Large system}}}
\put(38.00,55.00){\makebox(0,0)[cc]{system}}
\put(32.00,38.00){\makebox(0,0)[cc]{{\small system}}}
\put(31.00,33.00){\makebox(0,0)[cc]{{\tiny system}}}
\end{picture}
\end{center}
\caption{ Hierarchy of intrinsic perception.
 \label{l.fiss}}
\end{figure}
Of course, in general this observer cannot be a finite observer:
a complete description would only emerge in the limit of infinite
iterations
(cf. K. Popper's {``paradox of Tristram Shandy''}).
Finite observers cannot obtain complete self-comprehension.

 \subsection{Multi-automata configuration}

 The second kind of experiment operates with an {\em arbitrary number}
 of automaton copies.
 One automaton is a copy of another if both automata are
 isomorphic
  and if both are in the same initial state.
 With this configuration the experimenter is in the happy condition to
 apply as many input sequences to the original automaton as necessary.
 In a sense, the observer is not bound to ``observer-participancy,''
 because it is always possible
 to ``discard the used automaton copies,''
 and take a ``fresh'' automaton copy for further experiments.
 For an illustration, see Fig. \ref{f-a-experiment}.
\begin{figure}
\begin{center}
\unitlength=0.85mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(131.00,62.00)
\put(10.00,46.00){\framebox(121.00,16.00)[cc]{experimenter}}
\put(24.00,46.00){\vector(0,-1){19.00}}
\put(41.00,26.00){\vector(0,1){18.00}}
\put(25.00,37.00){\makebox(0,0)[lc]{input}}
\put(43.00,36.00){\makebox(0,0)[lc]{output}}
\put(58.00,46.00){\vector(0,-1){19.00}}
\put(75.00,26.00){\vector(0,1){18.00}}
\put(62.00,36.00){\makebox(0,0)[lc]{input}}
\put(80.00,35.00){\makebox(0,0)[lc]{output}}
\put(17.00,10.00){\framebox(29.00,16.00)[cc]{copy 1}}
\put(55.00,10.00){\framebox(25.00,16.00)[cc]{copy 2}}
\put(104.00,46.00){\vector(0,-1){19.00}}
\put(121.00,26.00){\vector(0,1){18.00}}
\put(108.00,36.00){\makebox(0,0)[lc]{input}}
\put(126.00,35.00){\makebox(0,0)[lc]{output}}
\put(97.00,10.00){\framebox(29.00,16.00)[cc]{copy N}}
\put(85.00,18.00){\circle*{0.00}}
\put(87.00,18.00){\circle*{0.00}}
\put(87.00,18.00){\circle*{0.00}}
\put(89.00,18.00){\circle*{0.00}}
\end{picture}
\end{center}
\caption{Schematic diagram of an experiment on an arbitrary
 number of identical automaton copies. \label{f-a-experiment}}
\end{figure}



 \section{Definition}

 In the foregoing section, important features of the
 extrinsic-intrinsic concept have been isolated in the context of
finite automata. A generalisation to arbitrary physical systems is
straightforward. The features will be
 summarised by the following definition.
 (Anything
 on which experiments can be performed
 will be called {\em system}. In particular, finite automata are
 systems.)

 An {\em intrinsic} quantity is
 associated
 with an experiment\\ {\it (i)} performed on a {\em single copy} of
 the system, \\ {\it (ii)} with the experimenter being part of
 the system.

 An {\em extrinsic}
 quantity, denoted by a tilde sign ``$\widetilde{\quad}$'' is
 associated with an experiment \\ {\it (i)}
 utilising, if necessary, an {\em arbitrary number of copies} of
 the system,
 \\
 {\it (ii)}
 with the experimenter not being part of the system.




 One may  ask whether, intuitively, the extrinsic point of
 view might be
 more appropriately represented by, stated pointedly,  the application
 of a ``can-opener''
 for the ``black box'' to see
 ``what's really in it.''
 Yet, while the physical realisation might be of some engineering
 importance, the primary concern is the
 phenomenology (i.e., the {\em experimental performance} of the
 system) and not how it is constructed.
 In this sense, the technological base of the automaton is
 irrelevant.
 For the same reason, i.e., because this is irrelevant to
 phenomenology, it is not important whether the automaton is in its
 minimal form.

 The requirement that in the extrinsic case an {\em arbitrary} number of
 system copies is available is equivalent to the statement that {\em no
 interaction takes place between the experimenter and the system}. (The
 reverse information flow from the observed system to the experimenter
 is necessary.)
This results in a one-way information flow
 in the extrinsic case:
   \def\A{\hbox{$\; \;$\rlap{/}\kern-.60em $\Longleftarrow$}}
$$
 {\rm system}
 \begin{array}{c}\Longrightarrow\\ \A\end{array}
{\rm  experimenter}   \qquad ,
$$
and a two-way information flow
in the intrinsic case:
$$
 {\rm system}
\Longleftrightarrow
{\rm  experimenter}   \qquad .
$$
An information
``backflow'' makes possible the application of
diagonalization techniques
  and also results in complementarity, which might be seen as a ``poor
man's version of diagonalization.''


 The definition applies to physical systems as well as to
 logics and (finite)
 automata. Automaton worlds provide an ideal ``playground'' for the
 study of certain algorithmic features related to undecidability, such
 as ``computational complementarity''
 and ``intrinsic
 indeterminism.''
 The {\em extrinsic-intrinsic problem} is the interrelation between
 extrinsic and intrinsic entities.


\section{Complementarity}
The input-output analysis of finite automata
yields a fresh insight into the quantum mechanical feature of
complementarity on a very elementary level.
Conversely,
the Copenhagen interpretation of quantum mechanics
\cite{jammer,wheeler-zurek} can be applied for the analysis of automata.
To substantiate this claim it is necessary to interrelate two strains
of investigation:
(i)
the lattice theoretic \cite{birkhoff} approach for a representation
of quantum physics, pioneered by G. Birkhoff and J. von Neumann
\cite{birkhoff-Neumann}
and later  extended to the calculus of propositions
\cite{jauch,piron} and
 orthomodular logic
\cite{kalmbach-83,kalmbach-86,pulmannova,giuntini};
(ii)
the theory of finite automata, in particular of Moore and Mealy
automata \cite{moore,mealy,conway,brauer-84}.
Computational complementarity in the automata context
 has been first investigated by
 E. F. Moore in his article {\sl Gedanken-Experiments on Sequential
 Machines}
 \cite{moore}.
Informally  stated,
 measurement of one aspect of an automaton
 makes impossible measurement of another aspect and {\it vice
versa}.
The name
{\em computational complementarity}
is due to
 D. Finkelstein
\cite{finkelstein-79,finkelstein-83}, who also made the first
attempt
to construct logics from experimentally obtained
propositions about automata; see also the more recent investigation
by A. A. Grib and
R. R. Zapatrin
 \cite{gribza}.
The following investigation has been carried out independently.
Although the goals are very similar, the methods and techniques
used here differ from the ones used by previous authors.


 The investigation is based on  the construction of
primitive
 {\em experimental statements} or {\em
propositions.} Then the {\em  structure} of these
propositions will be discussed, thereby defining
algebraic relations and operations between the propositions.
Although specific classes of finite automata will be analysed,
these considerations apply to universal computers as well.
(Finite automata can be simulated on universal computers.)


\subsection{Finite automata}
A {\em finite  (i,k,n)-automaton} has a finite number of i
 internal states, k input and n output symbols. It is characterised by
 its transition and output functions $\delta$ and $o$, which are often
represented by transition and output tables and by a diagram.
For an example see below.
 The output function
 of a {\em Moore-type automata}
depends solely on its internal state, whereas the output function of
 {\em Mealy-type automata}
 depends  on the input and the internal state.


\subsection{Automaton propositional calculi}
A finite automaton will be treated as a ``black box,'' whose transition
and output
 tables (i.e., informally speaking, its ``intrinsic machinery'') are
given in advance but
{\em whose initial state is unknown.}
Only {\em a single} copy of the automaton will be made available to the
experimenter.
 The  automaton is ``feeded'' with certain input sequences from
 the experimenter and responds with certain output sequences.
We shall be interested in
  the {\em distinguishing problem}:
{\em ``identify an unknown initial
 state.''}


Consider propositions of the form
 \begin{center}
 ``{\tt the automaton is in state} $a_j$''
 \end{center}
 with
 ($1\le j\le i$).
 Propositions can be composed to form expressions of the form
 \begin{center}
 ``{\tt the automaton is in state} $a_j$ {\tt or in state} $a_m$ {\tt
or  in state} $a_l  \cdots \quad .$''
 \end{center}
 Any proposition composed by propositions can be represented by a set.
 E.g., the above statement
 ``{\tt the automaton is in  state} $a_j$ {\tt or in state} $a_m$ {\tt
or  in state} $a_l  \cdots $''
 represents the set $\{
j,m,l,\ldots
\}$.
 The
 element ${\bf 1}$ is given by the set of {\em all} states $\{ 1,
 2,\ldots ,i\}$.
This corresponds to a proposition which is always satisfied:
 \begin{center}
 ``{\tt the automaton is in some internal state}''
 \end{center}


 The
 element ${\bf 0}$ is given by the {\em empty} set
$\emptyset$ (or $\{
\}$).
This corresponds to a proposition which is false (by definition the
automaton has to be in {\em some} internal state):
 \begin{center}
 ``{\tt the automaton is in no internal state}''
 \end{center}

 The class of all
 propositions and their relations will be called
 {\em automaton propositional calculus}
 and denoted by ${\frak A}$.
 Each particular outcome which, if defined, has the value ${\tt TRUE}$
or
${\tt FALSE}$, shall be called ``event.''
 In this sense, an automaton propositional calculus,  just as the
 quantum propositional calculus, is obtained {\em
 experimentally}.
 It consists of all potentially measurable {\em elements of the
 automaton reality} and their logical structure, with the implication
 as order relation.

The elementary propositions can be conveniently constructed by a
partitioning of automaton states generated from the input-output
analysis of the automaton as follows:
 Let
 $w=s_{1} s_{2} \cdots s_{k}$ be a sequence of input symbols,
 \begin{equation}
 a_{i,w} =
 a_{i}\delta_{s_{1}}(a_{i})\delta_{s_{2}}(\delta_{s_1}
 (a_{i}))\cdots \delta_{s_k}(\cdots \delta_{s_1}(a_{i})\cdots )
 \end{equation}
 and
 \begin{equation}
  z=o(a_{i,w})=
 o(a_{i})o(\delta_{s_{1}}(a_{i}))o(\delta_{s_{2}}(\delta_{s_1}
 (a_{i})))\cdots o(\delta_{s_k}(\cdots \delta_{s_1}(a_{i})\cdots ))\quad
.
 \end{equation}
 Let
 \begin{equation}
 \alpha_z^w=\{ a_i \mid
 o(a_{i,w})=z\}
 \end{equation}
 be the set of initial states which, on some fixed input sequence
 $w$ yield some fixed output
 sequence
 $z=t_{0}t_{1} t_{2} \cdots t_{k}$. I.e.,
 $\alpha_z^w$ is the equivalence class of propositions
 identifyable by input $w$ and output $z$.
 The elements $\{\alpha_z^w\}$ of the partition
 \begin{equation}
 v(w) = \bigcup_z \{ \alpha_z^w \}
 \end{equation}
 define the equivalence classes of propositions identifiable by input
 $w$ and output $z$.
 \begin{equation}
 V= \bigcup_w  v(w)=\{ v(\emptyset ),v(s_1),\ldots
 ,v(s_k),v(s_1s_2),\ldots \}\end{equation}
 is the set of partitions.

 Let $p_i$  be propositions
   of the
  form ``{\tt the automaton is in state} $a_i$.''
 The proposition
 \begin{equation}
 p_1\vee p_2
 \end{equation}
 (interpretable as ``$p_1$ or $p_2$'')
  defines a
 proposition of the
  form ``{\tt the automaton is in state} $a_1$ {\tt or}
 {\tt in state} $a_2$''
 (or the set theoretic union ``$p_1 \cup p_2$'')
 if and only if
 there exist input sequences $s_{j}\cdots s_{m}$
 such that $p_1 \vee p_2$ is
 identified by the partition $v(s_{j}\cdots s_{m})$.

 The proposition
 \begin{equation}
 p_j\wedge p_m
 \end{equation}
 (interpretable as ``$p_j$ and $p_m$'')
  defines a
 proposition of the
  form ``$p_j$ {\tt and}
 $p_m$''
 (or the set theoretic intersection ``$p_j\cap p_m$'')
 if and only if
 there exist input sequences $s_{j}\cdots s_{m}$
 such that $p_1 \wedge p_2$ is
 identified by the partition $v(s_{j}\cdots s_{m}$).


 The complement
 \begin{equation}
 \neg p_1
 \end{equation}
 (or $p_1'$) of a proposition $p_1$
 (has the meaning of ``not $p_1$'' and)
 is defined if and only if
 \begin{eqnarray*}
 p_1\wedge \neg p_1 &=& {\bf 0}\\
 p_1\vee \neg p_1 &=& {\bf 1}
 \end{eqnarray*}
 (or, with the propositions $p_1$ and $\neg p_1=p_j$ expressed as
 sets,  $p_1\cap p_j={\bf 0}=\emptyset$ and
  $p_1\cup p_j={\bf 1}=\{1,2,\ldots ,i\}$),
 and
 there exist input sequences $s_{j}\cdots s_{m}$
 such that $\neg p_1$
 is a proposition identified by the partition $v(s_j\cdots s_m)$.

 A {\em partial order relation} $p_j\preceq p_m$, or
 \begin{equation}
 p_j\rightarrow p_m
 \end{equation}
 (with the interpretation ``$p_j $ implies $p_m$,'' or
 with  ``whenever $p_j$ is true it
 follows that $p_m$ is true, too'')
 is defined if and only if
 $p_j $ {\tt implies}
 $p_m$, and
 there exist input sequences $s_{j}\cdots s_{m}$
 such that $p_j$ and $p_m$ are
 propositions identified by the partition $v(s_{j}\cdots s_{m})$.
 The partial order relation can be conveniently represented by drawing
 the Hasse diagram thereof. This can be done by proceeding in two
 steps. First, the Boolean lattices of propositional structures based
 on all relevant state partitions $v(w)$ are constructed.
 Then, the union of
 all these Boolean subalgebras renders the complete partial order of
 the automaton propositional calculus. This can also be understood
 graph theoretically \cite{harary-69,ore-62}.
 A {\sl Mathematica}
 package by Ch. Strnadl \cite{strnadl-package}
 can be obtained from the author.

\subsection{Example}
 For an explicit model of a
 non distributive and modular
 automaton
 propositional calculus
 consider the
 transition and output tables \ref{t-mealy-a} of a
(3,3,2)-automaton. Its diagram is drawn in Fig. \ref{fig:1}.
\begin{table}
\begin{tabular}{||c||ccc||}
 \hline\hline
   &  $1$ & $2$ & $3$  \\
 \hline
 $\delta_1$ &$1$&$1$&$1$\\
 $\delta_2$ &$2$&$2$&$2$\\
 $\delta_3$ &$3$&$3$&$3$\\
 \hline
 $o_1$ &1&0&0\\
 $o_2$ &0&1&0\\
 $o_3$ &0&0&1\\
 \hline\hline
\end{tabular}
\caption{Transition and output table of a
 (3,2,2)-automaton of the Mealy type.
 \label{t-mealy-a}}
 \end{table}
 \begin{figure}
\includegraphics[width=80mm]{ch-mea.ps}
 \caption{Diagram
 of  a  (3,2,2)-automaton
 of the Mealy type featuring
computational complementarity.
\label{fig:1}}
\end{figure}

 Input of 1, 2 or 3 steers the automaton into the respective state. At
 the same time, the output of the automaton is 1 only if the guess is a
 ``hit,'' i.e., if the automaton was in that state. Otherwise the
 output is 0.   After the measurement, the automaton is in a
 definite state, i.e., the state corresponding to the input symbol.
 If the guess has not been a
``hit,'' the information about
 the initial automaton state is lost.
 Therefore, the experimenter has to decide before carrying out the
measurement which one of the following
 hypotheses should be tested (in short-hand notation, ``$\{
1\}$'' stands for ``{\tt the automaton is in state} $1$'' {\it et
cetera}):
$
\{ 1 \}=
\neg
\{ 2,3 \},
\{ 2 \}=
\neg
\{ 1,3 \},
\{ 3 \}=
\neg
\{ 1,2 \}
$.
Measurement of either one of these three hypotheses (or their
complement) makes impossible measurement of the other two hypotheses.


No input, i.e., the empty input string $\emptyset$, identifies all three
internal automaton states. This corresponds to the trivial information
that the automaton is in {\em some} internal state.
Input of the symbol 1 (and all sequences of symbols starting with 1)
distinguishes between the hypothesis $\{1\}$ (output ``1'') and the
hypothesis
$\{2,3\}$ (output ``0'').
Input of the symbol 2 (and all sequences of symbols starting with 1)
distinguishes between the hypothesis $\{2\}$ (output ``1'') and the
hypothesis
$\{1,3\}$ (output ``0'').
Input of the symbol 3 (and all sequences of symbols starting with 1)
distinguishes between the hypothesis $\{3\}$ (output ``1'') and the
hypothesis
$\{1,2\}$ (output ``0'').
 The
  propositional calculus  is thus
 defined by the partitions
 \begin{eqnarray}
 v(\emptyset )&=&\{\{1,2,3\}\} \quad ,\\
 v(1 )&=&\{ \{1\} , \{2,3\}  \}\quad ,\\
 v(2 )&=&\{ \{2\} , \{1,3\}  \}\quad ,\\
 v(3 )&=&\{ \{3\} , \{1,2\}  \}\quad .
 \end{eqnarray}
 It can be represented by the lattice structure of Fig.
 \ref{f-mealy-a-i-p-c}.
 This lattice is of the ``Chinese latern'' $MO3$ form.
 It is non distributive, and it is a
pasting of three Boolean algebras $2^2$.
 \begin{figure}
\includegraphics[width=80mm]{ch-clt3.ps}
 \caption{Lattice $MO3$ of intrinsic propositional calculus
 of  a  (3,2,2)-automaton
 of the Mealy type.
\label{f-mealy-a-i-p-c}}
\end{figure}

 The obtained intrinsic propositional calculus
 in many ways  resembles the lattice obtained from photon polarisation
 experiments
 or from other incompatible quantum measurements.
Consider an experiment measuring photon polarisation.
 Then, three propositions  of the
form
``{\tt the  photon  has polarisation} $p_{\phi_1}$,'' ($i=1,2,3$),
 cannot be measured simultaneously for the angles $\phi_1 \neq
\phi_2\neq \phi_3
 ({\rm mod } \pi )$. An irreversible measurement of one direction of
polarisation would result in a state preparation, making impossible
measurement of the other directions of polarisation, and
resulting in a propositional calculus of the
 ``Chinese latern'' form $MO3$.


The
propositional calculi ${\frak F}_i$ of all Mealy-type automata with
$i$ internal
states can be constructed by combinatorical arguments
\cite{svozil-book}.
 Fig. \ref{f-hdxxx} shows ${\frak F}_4$, the Hasse diagrams of
 generic intrinsic  propositional calculi
 of Mealy automata up to 4 states.
\begin{figure}
\includegraphics[width=80mm]{ch-gal.ps}
\caption{The class ${\frak F}_4$ of non isomorphic Hasse diagrams
 of the intrinsic propositional calculi of generic 4-state
 automata of the Mealy type.
 \label{f-hdxxx}}
\end{figure}


\subsection{The inverse problem}
The previous paragraphs concentrated on the construction of a suitable
propositional calculus from the input-output analysis of an automaton.
The inverse problem is the construction of suitable automata which
correspond to (orthomodular) lattices, in particular to
subalgebras of Hilbert lattices.
Stated differently:
{\em ``given an arbitrary orthomodular (subalgebra of a Hilbert)
lattice ${\frak L}$;
is it possible to construct an automaton propositional calculus ${\frak
A}
$
realising ${\frak L}$?''}
If, as will be shown below, (for finite lattices) the question can be
decided positively and
constructively, then one obtains an explicit automaton model for every
arbitrary quantum system (but not {\it vice versa}).


Let an {\em orthomodular lattice} be a lattice satisfying the
orthomodular law, and let a {\em Hilbert lattice} be the lattice
of all closed subspaces of a Hilbert space, with the ``infimum''
operator defined by the intersection of subspaces, the ``supremum''
operator defined by the closure of the linear span of subspaces and
the orthocomplement defined by the orthogonal subspace.
 Any finite
 (``finite''
 means
that the lattice has a finite number of elements)
 orthomodular
 lattice is isomorphic (1-1 translatable) to some finite  (lattice)
automaton
 propositional calculus. I.e.,
 \begin{equation}
 {\rm finite orthomodular lattice}
 \begin{array}{c}\Rightarrow\\ \Leftarrow
\end{array}
{\rm finite automaton propositional calculus}
 \end{equation}
Threfore,
 any finite orthomodular subalgebra of a Hilbert
 lattice is isomorphic (1-1 translatable) to some finite automaton
 propositional calculus. I.e.,
 \begin{equation}
\left\{ \begin{array}{c}
{ \rm finite orthomodular subalgebra }\\
{\rm of Hilbert lattice (quantum logic) }
\end{array} \right\}
 \begin{array}{c}\Rightarrow\\ \Leftarrow \end{array}
{\rm finite automaton propositional calculus}
\end{equation}

An actual proof of these statements is too technical and will be given
elsewhere \cite{svozil-book}.
It makes use of the fact that
every orthomodular lattice is a
pasting
of its maximal Boolean subalgebras, also called {\em blocks}
\cite{kalmbach-83,Navara}.
These blocks can be elegantly represented by
sets of partitions of automata states, because
``at face value,'' every automaton state partition $v(\cdots
)$ with
$n$ elements generates a Boolean algebra $2^n$. If one identifies
these Boolean algebras with blocks, the
set of automaton state partitions $V$ represents a complete
family of blocks of the automaton propositional calculus.


\subsection{Discussion}
Strictly speaking, automaton models for quantum systems
correspond to nonlocal hidden variable models.
The ``hidden'' physical entities are the ``true'' initial states
of automata.

It is not entirely unreasonable to speculate about logico-algebraic
structures of automaton universes in general. To put it pointedly, one
could ask
{\em ``how would creatures embedded in a universal computer perceive
their universe?''}
The lattice-theoretic  answer might be as follows. Let
${\frak F}_i$ stand for the family of all intrinsic propositional calculi
of automata with $i$ states.
 From the point
of view of logic, the intrinsic propositional calculi of a
universe
generated by
universal computation
is the limiting class  $\lim_{n\rightarrow \infty }{\frak F}_n$ of
all automata with $n \rightarrow \infty$ states.
Since
$
{\frak F}_1
\subset
{\frak F}_2
\subset
{\frak F}_3
\subset
\cdots
\subset
{\frak F}_i
\subset
{\frak F}_{i+1}
\subset
\cdots
$, this class ``starts with'' the propositional calculi represented by
Fig.
 \ref{f-hdxxx}, p.
 \pageref{f-hdxxx}.


It is tempting to speculate that we live in a computer
generated universe. But then, if the ``underlying'' computing
agent were universal,
{\em there
is no {\it a priori} reason to exclude propositional calculi even if
they
do not correspond to an orthomodular subalgebra of a Hilbert lattice.}
I.e., to test the speculation that we live in a universe created by
universal computation,
we
would have to look for phenomena which correspond
to automaton propositional calculi not contained in the subalgebras of
some
Hilbert space --- such as, for instance,  the one represented by Fig.
 \ref{f:noa.pic2}, p.
 \pageref{f:noa.pic2}, which was obtained from  the state partition
$
\{\{\{1\}, \{2\}, \{3, 4\}\},  \{\{1\}, \{2, 4\}, \{3\}\}, \{\{1, 2\},
\{3\}, \{4\}\},
   \{\{1, 3\}, \{2\}, \{4\}\}\}
$.
\begin{figure}
\includegraphics[width=80mm]{ch-octo.ps}
\caption{Hasse diagram of an algebraic structur which is neither a
lattice nor a partial order.
 \label{f:noa.pic2}}
\end{figure}

\begin{thebibliography}{999}

 \bibitem{roessler-87}
 O. E. R\"ossler, {\sl Endophysics}, in {\sl Real Brains, Artificial
 Minds}, ed. by J. L. Casti and A. Karlquist (North-Holland, New
 York, 1987), p. 25.


 \bibitem{roessler-92}
 O. E. R\"ossler, {\sl Endophysics, Die Welt des inneren Beobachters},
 ed. by P. Weibel (Merwe Verlag, Berlin, 1992).

 \bibitem{roessler-922}
 O. E. R\"ossler, {\sl talk at the Endophysics Symposium} (Linz,
Austria, June 1992).

 \bibitem{putnam:81}
H. Putnam,
{\sl Reason, Truth and History}
(Cambridge University Press,
Cambridge, 1981).

 \bibitem{popper-50}
 K. R. Popper, {\sl The British Journal for the Philosophy of Science}
 {\bf 1}, 117, 173 (1950).

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

 \bibitem{primas-88}
 H. Primas, {\sl Time-asymmetric phenomena in Biology} (ETH preprint,
 1988).

\bibitem{svo-83}
 K. Svozil,
 {\sl On the setting of scales for space and time in arbitrary
 quantized media}, {\sl Lawrence Berkeley Laboratory preprint,
 LBL-16097,} May 1983.

\bibitem{svo-86}
K. Svozil,
 {\sl Il Nuovo Cimento} {\bf 96B}, 127 (1986).

\bibitem{svo5}
K. Svozil,
{\sl Europhysics Letters} {\bf 2}, 83 (1986)

\bibitem{sv4}
 K. Svozil,
{\sl J. Phys.} {\bf A19}, L1125 (1986).

 \bibitem{wheeler}
 J. A. Wheeler, {\sl Law without law}, in {\sl
 Quantum Theory and Measurement}, ed. by J. A. Wheeler and W. H. Zurek
 (Princeton University Press, Princeton, 1983),
 p. 182.

 \bibitem{epr}
 A. Einstein, B. Podolsky and N. Rosen, {\sl Phys. Rev.} {\bf 47}, 777
 (1935).

 \bibitem{peres}
 A. Peres and W. H. Zurek, Am. J. Phys., {\bf 50}, 807 (1982).

 \bibitem{peres-85}
 A. Peres, {\sl Found. Phys.} {\bf 15}, 201 (1985).

 \bibitem{rothstein}
 J. Rothstein, International Journal of Theoretical Physics {\bf 21},
 327 (1982).

 \bibitem{ginsburg-58}
 S. Ginsburg, {\sl Journal of the Association for Computing Machinery}
 {\bf 5}, 266 (1958).

 \bibitem{gill-61}
 A. Gill, {\sl Information and Control} {\bf 4}, 132 (1961).




\bibitem{jammer}
M. Jammer,
{\sl The Philosophy of Quantum Mechanics} (John Wiley, New York 1974).

 \bibitem{wheeler-zurek}
 J. A. Wheeler and W. H. Zurek,
 {\sl Quantum Theory and Measurement},
 (Princeton University Press, Princeton, 1983).

 \bibitem{birkhoff}
 G. Birkhoff, {\em Lattice Theory, Second Edition} (American
 Mathematical Society, New York, 1948).

 \bibitem{birkhoff-Neumann}
 G. Birkhoff and J. von  Neumann, {\sl Annals of Mathematics} {\bf 37},
 823 (1936).

\bibitem{jauch}
 J. M. Jauch, {\sl Foundations of Quantum Mechanics} (Addison-Wesley,
 Reading, Massachusetts, 1968).

 \bibitem{piron}
 C. Piron, {\sl Foundations of Quantum Physics} (W. A. Benjamin,
 Reading, MA, 1976).

 \bibitem{kalmbach-83}
 G. Kalmbach, {\sl Orthomodular Lattices} (Academic Press, New York,
 1983).

 \bibitem{kalmbach-86}
 G. Kalmbach, {\sl Measures and Hilbert Lattices} (World Scientific,
Singapore, 1986).

 \bibitem{pulmannova}
 P. Pt\'ak and S. Pulmannov\'a,
 {\sl Orthomodular Structures as Quantum Logics}
 (Kluwer Academic Publishers, Dortrecht, 1991).

 \bibitem{giuntini}
R. Giuntini, {\sl Quantum Logic and Hidden Variables}
(BI
Wisseschaftsverlag, Mannheim, 1991).

 \bibitem{mealy}
 J. E. Hopcroft and J. D. Ullman,
 {\sl Introduction to Automata Theory, Languages, and Computation}
 (Addison-Wesley, Reading, MA, 1979).

 \bibitem{conway}
 J. H. Conway, {\sl Regular Algebra and Finite Machines} (Chapman and
 Hall Ltd., London, 1971).

 \bibitem{brauer-84}
 W. Brauer, {\sl Automatentheorie} (Teubner, Stuttgart, 1984).

 \bibitem{finkelstein-79}
 D. Finkelstein,
 {\sl Holistic Methods in Quantum Logic}, in {\sl Quantum Theory and
 the Structures of Time and Space, Volume 3}, ed. by L. Castell and C.
 F. von Weizs\"acker (Carl Hanser Verlag, M\"unchen, 1979), p. 37.


 \bibitem{finkelstein-83}
 D. Finkelstein and S. R. Finkelstein,
 {\sl International Journal of Theoretical Physics} {\bf 22}, 753
 (1983).

\bibitem{gribza}
A. A. Grib and
R. R. Zapatrin,
{\sl International Journal of Theoretical Physics} {\bf 29}, 113 (1990);
{\it ibid.} {\bf 31}, 1669 (1992).

 \bibitem{turing}
 A. M. Turing, {\sl Proc. London Math. Soc.} {\bf (2), 42}, 230
 (1936-7).

\bibitem{rogers}
H. Rogers, {\sl Theory of Recursive Functions and Effective
Computability} (MacGraw-Hill, New York 1967)

 \bibitem{gould}
 E. M. Gould, {\sl Information and Control} {\bf 10}, 447 (1967).

 \bibitem{harary-69}
 F. Harary, {\sl Graph Theory} (Addison-Wesley, Reading, MA, 1969).

 \bibitem{ore-62}
 O. Ore, {\sl Theory of Graphs} (American Mathematical Society,
 New York, 1962).

\bibitem{strnadl-package}
Ch. Strnadl, {\sl Mathematica package for automaton analysis}, available
from the author (K.S.) on request or by anonymous ftp ({\tt
ftp.univie.ac.at/packages/mathematica/automata.m}).

\bibitem{svozil-book}
K. Svozil, {\sl Randomness \& Undecidability in Physics}
(World Scientific, Singapore, to be published 1993).

\bibitem{Navara}
M. Navara and V. Rogalewicz, {\sl Math. Nachr.} {\bf 154}, 157 (1991).

\end{thebibliography}

\end{document}