\documentstyle[12pt]{article}
%\documentstyle{llncs}
\begin{document}
\title{The {C}hurch-{T}uring thesis as a guiding principle for
physics}
\author{Karl Svozil\\
Institut f\"ur Theoretische Physik  \\
University of Technology Vienna      \\
Wiedner Hauptstra\ss e 8-10/136    \\
A-1040 Vienna, Austria              \\
e-mail: svozil@tph.tuwien.ac.at\\
www: http://tph.tuwien.ac.at/$\widetilde{\;}$svozil}
\date{ }
\maketitle

%\begin{flushright}
%{\scriptsize
%http://tph.tuwien.ac.at/$\widetilde{\;}$svozil/publ/ct.tex}
%\end{flushright}

\begin{abstract}
Two aspects of the physical side of the Church-Turing
thesis are discussed.
The first issue is a variant of the Eleatic argument against motion,
dealing with Zeno squeezed time cycles of computers.
The second argument reviews the issue of one-to-one computation, that
is, the bijective (unique and reversible) evolution of computations and
its relation to the measurement process.
\end{abstract}


\section{Introduction}
It is reasonable to require
from a ``useful'' theory of computation that any
capacity and feature of physical systems (interpretable as ``computing
machines'') should be reflected therein and
{\it vice versa.}

The recognition of the physical aspect of the Church-Turing thesis---the
postulated equivalence between the informal notion of ``mechanical
computation'' (algorithm) and recursive function theory as its formalized
counterpart---is not new
\cite{scilard-col,brillouin1,brillouin2,maxwell-demon,rogers1,odi:89}. In particular
Landauer
points out that computers are physical systems, that computations are
physical processes and therefore are subject to the laws of physics
\cite{landauer:61,landauer-67,landauer:82,landauer-87,landauer-88,landauer-89,landauer,landauer-94,landauer-95}.
 As Deutsch puts it \cite[p. 101]{deutsch},
 \begin{quote}
 {\em
 ``The reason why we find it possible to construct, say, electronic
 calculators, and indeed why we can perform mental arithmetic, cannot
 be found in mathematics or logic. {\em
 The reason is that the laws of physics `happen to' permit the
 existence of physical models for the operations of arithmetic}
 such as addition, subtraction and multiplication.
 If they did not, these familiar operations would be
 noncomputable functions. We might still
 know {\em of} them and invoke them in mathematical proofs
 (which would presumably be called `nonconstructive') but we could
 not perform them.''
 }
 \end{quote}
See also Pitowsky's review \cite{pit:90}.
One may indeed perceive a strong interrelationship between the way we do
mathematics, formal logic, the computer sciences and physics. All these
sciences have been developed and constructed by us in the context of our
(everyday) experiences.

The Computer Sciences are well aware of this
connection. See, for instance,
Odifreddi's review
\cite{odi:89}, the articles by
 Rosen \cite{rosen} and Kreisel \cite{kreisel},
 or
 Davis'
 book \cite[p. 11]{davis-58}, where the following question is
asked:
 \begin{quote}
 {\em `` $\ldots$ how can we ever exclude the possibility of our
 presented,
 some day (perhaps by some extraterrestrial visitors), with a (perhaps
 extremely complex) device or ``oracle'' that ``computes'' a
 noncomputable function?''
 }
 \end{quote}

Thus, it comes as no surprise that the Church-Turing thesis is under
permanent attack from the physical sciences. For just two such attempts
in the recent literature, we refer to the articles by Siegelmann
\cite{siegel95} and Hogarth \cite{hogarth1,hogarth2}.

Even more so, this applies  to the weak Church-Turing thesis, often
referred to as ``Cook-Karp thesis,'' putting into question the
robustness of the notion of tractability or polynomial time complexity
class
with respect to variations of ``reasonable'' models of computation.
One particular famous contemporary case is quantum computing.
There, it has been shown that at least factoring may require polynomial
time on quantum computers within
``reasonable statistics'' \cite{shor:94,ekerj96}.

We shall take out two examples of connections between physics and
computation. First, we briefly review reformulations of Zeno's argument
of Achilles
and the Tortoise (Hector). This paradox purportedly seems to have been
originally directed against motion \cite{zeno,ki-57,gruenbaum:68}.
In this context it can be applied against the uncritical
use of continua and dense sets in general.
Later on, we
shall investigate reversible
computations, more specifically computations corresponding to
bijective (one-to-one)
maps and its possible connections with measurement operations.


\section{Infinity machines by Zeno squeezed time cycles}

In what follows, an
{\em oracle} problem
 solver will be introduced
whose capacity exceeds  and outperforms any presently
 realisable, finite machine and also  any
 universal computer such as the Turing machine. We follow
previous discussions
(cf. \cite[pp. 24-27]{svozil-93} and
\cite{svozil-nat-acad,svozil-complexity:95,svozil-set,maryland}).

 Its
 design is based upon
 a universal computer with ``squeezed'' cycle times of
 computation according to a geometric progression.
 The only difference
between universal computation
 and this type of
 oracle computation is the speed of execution. But what a difference
indeed: Zeno squeezed oracle
 computation performs
 computations {\em in the limit of infinite time of computation}.
 In order to achieve this limit,
 two time scales are introduced: the {\em intrinsic time scale
 of the process of computation}, which approaches infinity in finite
{\em
 extrinsic or proper time of some outside observer}.

As a consequence, certain tasks which lie beyond the domain of recursive
function theory  become computable and even tractable. For example, the
halting problem
and any problem codable into a halting problem would become solvable.
It would also be possible to produce an otherwise
 uncomputable and random output---equivalent to the tossing of a fair
 coin---such as Chaitin's $\Omega$ \cite{chaitin:92,calude:94}
 in finite proper time. We shall come back to these issues, in
particular consistency, shortly.

 A very similar setup has been introduced by Hermann Weyl
 \cite{weyl:49}, which was discussed
 by
 Gr\"unbaum
\cite[p. 630]{gruenbaum:74}.
Already Weyl raised the question whether it is kinematically feasible
for a machine to carry out an {\em infinite} sequence of operations in
{\em finite} time.
Weyl writes \cite[p. 42]{weyl:49},
\begin{quote}
Yet, if the segment of length 1 really consists of infinitely many
sub-segments of length 1/2, 1/4, 1/8,
$\ldots$, as of `chopped-off' wholes, then it is incompatible with the
character of the infinite as the `incompletable' that Achilles should
have been able to traverse them all. If one admits this possibility,
then there is no reason why a machine should not be capable of
completing an infinite sequence of distinct acts of decision within a
finite amount of time; say, by supplying the first result after 1/2
minute, the second after another 1/4 minute, the third 1/8 minute later
than the second, etc. In this way it would be possible, provided the
receptive power of the brain would function similarly, to achieve a
traversal of all natural numbers and thereby a sure yes-or-no decision
regarding any existential question about natural numbers!
\end{quote}

See also
the articles by Thomson \cite{thom:54}, Benacerraf \cite{benna:62},
Rucker \cite{rucker},
Pitowsky \cite{pit:90}, Earman and Norton \cite{ear-nor:93} and Hogarth
\cite{hogarth1,hogarth2},
as well as
 E. W. Beth,
 \cite[p. 492]{beth-59}
 and
K. L\'opez-Escobar
 \cite{le-91}.

 Let us come back to the original goal: the construction of a
``Zeno squeezed oracle,''
 or, in Gr\"unbaum's terminology, of an  ``infinity machine.''
As sketched before, it
can be conceived by considering two
time scales $\tau$ and $t$
which are related as follows.
\begin{description}
\item[$\bullet$]
The
 {\em proper time} $\tau$ measures the physical system time by clocks
 in a way similar to the usual operationalisations; whereas
\item[$\bullet$]
 a discrete {\it cycle time} $t=0,1,2,3,\ldots$ characterizes a sort of
 ``intrinsic'' time scale for a process  running on an otherwise
universal machine.
\item[$\bullet$]
 For some  unspecified
 reason we assume that this machine would allow us to
 ``squeeze'' its intrinsic time  $t$  with respect to the proper time
 $\tau$ by a geometric progression. Hence, for $k<1$, let
 any time cycle of $t$, if measured in terms of $\tau$, be squeezed by
 a factor of $k$ with respect to the foregoing time cycle
i.e.,
 \begin{eqnarray}
 \tau_0&=&0,\quad \tau_1=k ,\quad \tau_{t+1}-\tau_t =k(\tau_t
-\tau_{t-1}),
\\
 \tau_{t}&=&\sum_{n=0}^tk^n-1={k(k^t-1)\over k-1}\quad .
 \end{eqnarray}
Thus, in the limit
 of infinite cycle time $t\rightarrow \infty$, the proper time
 $\tau_\infty = k/(1-k)$ remains finite.
\end{description}
We just mention that for the model introduced here
only
dense space-time would be required.

There is no commonly accepted principle which would forbid
such an oracle {\it a priori}. In particular, classical mechanics
postulates space and time continua as a foundational principle. One
might argue that such an oracle would require a geometric
energy increase  resulting in an infinite consumption of energy. Yet, no
currently accepted physical principle
excludes us from assuming that every geometric
decrease
in cycle time could be associated with a geometric progression in energy
consumption, at least up to some limiting (e.g., Planck) scale.

Nevertheless,
it can be shown by a
diagonalization argument that the
application of
such oracle subroutines
would result in a paradox.
The paradox is constructed in the context of the halting problem.
It is formed in a similar manner as Cantor's diagonalization
argument.
Consider an arbitrary algorithm $B(x)$ whose input is a string of
symbols
$x$.
 Assume that there exists (wrong) an ``effective halting algorithm''
 ${ HALT}$, implementable on the oracle described above,
 which  is
 able to decide whether $B$ terminates on $x$ or not.

 Using  ${ HALT}(B(x))$ we shall construct another
 deterministic computing agent
$A$, which
 has as input any effective program $B$ and which proceeds as follows:
 Upon reading the program $B$ as input, $A$ makes a copy of it.
 This  can be readily achieved, since
 the program $B$ is presented to $A$  in some
 encoded form $\# (B)$, i.e., as a string of symbols. In the next
 step, the agent uses the
 code $\# (B)$ as input string for $B$ itself; i.e., $A$  forms
 $B(\#(B))$, henceforth denoted by $B(B)$. The agent now hands
 $B(B)$ over to its
 subroutine ${ HALT}$.
 Then, $A$ proceeds as follows:
  if ${ HALT}(B(B))$ decides that $B(B)$
 halts, then the agent
 $A$ does not halt;
this can for instance be realized by an infinite {
 DO}-loop;
  if ${ HALT}(B(B))$ decides that $B(B)$
 does {\em not} halt, then
 $A$ halts.

 We shall now confront the agent $A$ with a paradoxical task by
 choosing $A$'s own code as input for itself.---Notice
 that $B$ is arbitrary and has not yet been specified and we are
totally justified to do that:
The deterministic agent $A$ is representable by an algorithm with code
$\# (A)$. Therefore, we are free to substitute $A$ for $B$.

Assume that classically $A$ is restricted to classical bits of
information.
Then, whenever
 $A(A)$ halts,  ${ HALT}(A(A))$  forces
 $A(A)$ not to halt.
Conversely, whenever $A(A)$ does not halt, then ${ HALT}(A(A))$
 steers $A(A)$
 into the halting mode. In both cases one arrives at a
complete contradiction.

Therefore, at least in this example, too powerful physical models (of
computation) are inconsistent.
It almost goes without saying that the concept of infinity
machines is neither constructive nor operational in the current physical
framework.



Quantum mechanics offers a rescue;
yet in a form which is not common in ``classical'' recursion theory.
The paradox is resolved when
$A$ is allowed a nonclassical qubit of information.
Classical information theory is based on the
classical bit as
fundamental atom.
Any classical bit is in one of two
classical states $t$ (often interpreted as ``true'') and $f$ (often
interpreted as ``false'').
In quantum information theory
the most elementary unit of information is
 the {\em quantum bit,}
henceforth called {\em qubit}.
Qubits can be physically represented by a coherent
superposition
of two orthonormal quantum
 states $t$ and $f$.
The quantum bit states
$$
\vert a,b\rangle
=
a\left( \begin{array}{c}1\\ 0\end{array} \right)+
b\left( \begin{array}{c}0\\ 1\end{array} \right)
=
a\vert 0\rangle +b\vert 1 \rangle ,
$$
with
$ \vert a\vert^2+\vert b\vert^2=1$, $a,b\in { C}$
form a continuum.

Assume now that
$\vert 0\rangle =
\vert 1,0\rangle
$
and $\vert 1\rangle =
\vert 0,1\rangle
$
 correspond to the halting and to the nonhalting
states, respectively.
$A$'s task can consistently be performed
if it inputs a qubit corresponding to the {\em fixed point} state
of the diagonalization ($not$) operator
$$
\widehat{D}= not=
\tau_1 =
\left(
\begin{array}{cc}
0 & 1\\
1 & 0
\end{array}
\right) =\vert 1\rangle \langle 0\vert
+ \vert 0\rangle \langle 1\vert    .
$$
That is,
\begin{equation}
\widehat{D}\vert \ast \rangle =\vert \ast \rangle  .
\end{equation}
The fixed point state $\vert \ast \rangle $ is
just the eigenstate of the diagonalization operator
$\widehat{D}$ with
eigenvalue $1$.
Notice that the eigenstates of
$\widehat{D}$ are
\begin{equation}
\vert I\rangle      ,
\vert II\rangle
=
{1\over \sqrt{2}}\left[
\left( \begin{array}{c}1\\ 0\end{array} \right)\pm
\left( \begin{array}{c}0\\ 1\end{array} \right)
\right]
=
{1\over \sqrt{2}}(\vert 0\rangle \pm \vert 1\rangle )
\end{equation}
with the  eigenvalues $+1$ and $-1$, respectively.
Thus, the nonparadoxical, fixed point qubit
in the basis of $\vert 0\rangle $ and $\vert 1\rangle $ is given by
\begin{equation}
\vert \ast \rangle =\vert {1\over \sqrt{2}},{1\over \sqrt{2}} \rangle
=\vert I\rangle .
\end{equation}
In natural language,
this qubit solution corresponds to the statement that
it is impossible
for the agent to control the outcome, since
 there is a
fifty percent chance for each of the  classical bit states $\vert
0\rangle$ and
$\vert 1\rangle$ to be ``stimulated'' at
$t_{A}$.
The impossibility of outcome control
is
indeed encountered
in quantum mechanics.
Stated differently: at the level of probability amplitudes, quantum
theory permits a Zeno squeezed oracle.  But at the level
of observable
probabilities, this is exactly nullified, as
the result of the computation
 appears to
occur entirely at random.


\section{One-to-one computational paths and measurement}

The connection between information and physical entropy, in particular
the entropy increase during computational steps corresponding to an
irreversible loss of information---deletion or other many-to-one
operations---has raised considerable attention in the physics community
\cite{maxwell-demon}.
Figure \ref{f-rev-comp}  \cite{landauer-94} depicts a flow diagram,
illustrating the
difference between one-to-one, many-to-one and one-to-many computation.
\begin{figure}
\begin{center}
%TexCad Options
%\grade{\off}
%\emlines{\off}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{0.20}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{0.10}
\unitlength 0.50mm
\linethickness{0.4pt}
\begin{picture}(191.00,95.00)
\put(10.00,10.00){\circle*{2.00}}
\put(20.00,10.00){\circle*{2.00}}
\put(30.00,10.00){\circle*{2.00}}
\put(40.00,10.00){\circle*{2.00}}
\put(10.00,20.00){\circle{2.00}}
\put(10.00,11.00){\vector(0,1){8.00}}
\put(10.00,30.00){\circle{2.00}}
\put(10.00,21.00){\vector(0,1){8.00}}
\put(10.00,40.00){\circle{2.00}}
\put(10.00,31.00){\vector(0,1){8.00}}
\put(10.00,50.00){\circle{2.00}}
\put(10.00,41.00){\vector(0,1){8.00}}
\put(10.00,60.00){\circle{2.00}}
\put(10.00,51.00){\vector(0,1){8.00}}
\put(10.00,70.00){\circle{2.00}}
\put(10.00,61.00){\vector(0,1){8.00}}
\put(10.00,80.00){\circle{2.00}}
\put(10.00,71.00){\vector(0,1){8.00}}
\put(10.00,90.00){\circle{2.00}}
\put(10.00,81.00){\vector(0,1){8.00}}
\put(20.00,20.00){\circle{2.00}}
\put(20.00,11.00){\vector(0,1){8.00}}
\put(20.00,30.00){\circle{2.00}}
\put(20.00,21.00){\vector(0,1){8.00}}
\put(20.00,40.00){\circle{2.00}}
\put(20.00,31.00){\vector(0,1){8.00}}
\put(20.00,50.00){\circle{2.00}}
\put(20.00,41.00){\vector(0,1){8.00}}
\put(20.00,60.00){\circle{2.00}}
\put(20.00,51.00){\vector(0,1){8.00}}
\put(20.00,70.00){\circle{2.00}}
\put(20.00,61.00){\vector(0,1){8.00}}
\put(20.00,80.00){\circle{2.00}}
\put(20.00,71.00){\vector(0,1){8.00}}
\put(20.00,90.00){\circle{2.00}}
\put(20.00,81.00){\vector(0,1){8.00}}
\put(30.00,20.00){\circle{2.00}}
\put(30.00,11.00){\vector(0,1){8.00}}
\put(30.00,30.00){\circle{2.00}}
\put(30.00,21.00){\vector(0,1){8.00}}
\put(30.00,40.00){\circle{2.00}}
\put(30.00,31.00){\vector(0,1){8.00}}
\put(30.00,50.00){\circle{2.00}}
\put(30.00,41.00){\vector(0,1){8.00}}
\put(30.00,60.00){\circle{2.00}}
\put(30.00,51.00){\vector(0,1){8.00}}
\put(30.00,70.00){\circle{2.00}}
\put(30.00,61.00){\vector(0,1){8.00}}
\put(30.00,80.00){\circle{2.00}}
\put(30.00,71.00){\vector(0,1){8.00}}
\put(30.00,90.00){\circle{2.00}}
\put(30.00,81.00){\vector(0,1){8.00}}
\put(40.00,20.00){\circle{2.00}}
\put(40.00,11.00){\vector(0,1){8.00}}
\put(40.00,30.00){\circle{2.00}}
\put(40.00,21.00){\vector(0,1){8.00}}
\put(40.00,40.00){\circle{2.00}}
\put(40.00,31.00){\vector(0,1){8.00}}
\put(40.00,50.00){\circle{2.00}}
\put(40.00,41.00){\vector(0,1){8.00}}
\put(40.00,60.00){\circle{2.00}}
\put(40.00,51.00){\vector(0,1){8.00}}
\put(40.00,70.00){\circle{2.00}}
\put(40.00,61.00){\vector(0,1){8.00}}
\put(40.00,80.00){\circle{2.00}}
\put(40.00,71.00){\vector(0,1){8.00}}
\put(40.00,90.00){\circle{2.00}}
\put(40.00,81.00){\vector(0,1){8.00}}
\put(50.00,10.00){\circle*{2.00}}
\put(50.00,20.00){\circle{2.00}}
\put(50.00,11.00){\vector(0,1){8.00}}
\put(50.00,30.00){\circle{2.00}}
\put(50.00,21.00){\vector(0,1){8.00}}
\put(50.00,40.00){\circle{2.00}}
\put(50.00,31.00){\vector(0,1){8.00}}
\put(50.00,50.00){\circle{2.00}}
\put(50.00,41.00){\vector(0,1){8.00}}
\put(50.00,60.00){\circle{2.00}}
\put(50.00,51.00){\vector(0,1){8.00}}
\put(50.00,70.00){\circle{2.00}}
\put(50.00,61.00){\vector(0,1){8.00}}
\put(50.00,80.00){\circle{2.00}}
\put(50.00,71.00){\vector(0,1){8.00}}
\put(50.00,90.00){\circle{2.00}}
\put(50.00,81.00){\vector(0,1){8.00}}
\put(80.00,10.00){\circle*{2.00}}
\put(90.00,10.00){\circle*{2.00}}
\put(100.00,10.00){\circle*{2.00}}
\put(110.00,10.00){\circle*{2.00}}
\put(80.00,20.00){\circle{2.00}}
\put(80.00,11.00){\vector(0,1){8.00}}
\put(80.00,30.00){\circle{2.00}}
\put(80.00,21.00){\vector(0,1){8.00}}
\put(90.00,20.00){\circle{2.00}}
\put(90.00,11.00){\vector(0,1){8.00}}
\put(90.00,30.00){\circle{2.00}}
\put(90.00,21.00){\vector(0,1){8.00}}
\put(100.00,20.00){\circle{2.00}}
\put(100.00,11.00){\vector(0,1){8.00}}
\put(100.00,30.00){\circle{2.00}}
\put(100.00,21.00){\vector(0,1){8.00}}
\put(100.00,40.00){\circle{2.00}}
\put(100.00,31.00){\vector(0,1){8.00}}
\put(100.00,50.00){\circle{2.00}}
\put(100.00,41.00){\vector(0,1){8.00}}
\put(100.00,60.00){\circle{2.00}}
\put(100.00,51.00){\vector(0,1){8.00}}
\put(100.00,70.00){\circle{2.00}}
\put(100.00,61.00){\vector(0,1){8.00}}
\put(100.00,80.00){\circle{2.00}}
\put(100.00,71.00){\vector(0,1){8.00}}
\put(100.00,90.00){\circle{2.00}}
\put(100.00,81.00){\vector(0,1){8.00}}
\put(110.00,20.00){\circle{2.00}}
\put(110.00,11.00){\vector(0,1){8.00}}
\put(110.00,30.00){\circle{2.00}}
\put(110.00,21.00){\vector(0,1){8.00}}
\put(110.00,40.00){\circle{2.00}}
\put(110.00,31.00){\vector(0,1){8.00}}
\put(110.00,50.00){\circle{2.00}}
\put(110.00,41.00){\vector(0,1){8.00}}
\put(120.00,10.00){\circle*{2.00}}
\put(120.00,20.00){\circle{2.00}}
\put(120.00,11.00){\vector(0,1){8.00}}
\put(120.00,30.00){\circle{2.00}}
\put(120.00,21.00){\vector(0,1){8.00}}
\put(120.00,40.00){\circle{2.00}}
\put(120.00,31.00){\vector(0,1){8.00}}
\put(120.00,50.00){\circle{2.00}}
\put(120.00,41.00){\vector(0,1){8.00}}
\put(80.00,31.00){\vector(2,1){18.67}}
\put(90.00,31.00){\vector(1,1){8.67}}
\put(110.00,51.00){\vector(-1,1){8.67}}
\put(119.67,51.00){\vector(-2,1){18.00}}
\put(10.00,5.00){\makebox(0,0)[cc]{$p_1$}}
\put(20.00,5.00){\makebox(0,0)[cc]{$p_2$}}
\put(30.00,5.00){\makebox(0,0)[cc]{$p_3$}}
\put(40.00,5.00){\makebox(0,0)[cc]{$p_4$}}
\put(50.00,5.00){\makebox(0,0)[cc]{$p_5$}}
\put(80.00,5.00){\makebox(0,0)[cc]{$p_1$}}
\put(90.00,5.00){\makebox(0,0)[cc]{$p_2$}}
\put(100.00,5.00){\makebox(0,0)[cc]{$p_3$}}
\put(110.00,5.00){\makebox(0,0)[cc]{$p_4$}}
\put(120.00,5.00){\makebox(0,0)[cc]{$p_5$}}
\put(5.00,95.00){\makebox(0,0)[cc]{a)}}
\put(75.00,95.00){\makebox(0,0)[cc]{b)}}
\put(145.00,95.00){\makebox(0,0)[cc]{c)}}
\put(170.00,90.00){\circle{2.00}}
\put(170.00,80.00){\circle{2.00}}
\put(170.00,70.00){\circle{2.00}}
\put(170.00,60.00){\circle{2.00}}
\put(170.00,50.00){\circle{2.00}}
\put(170.00,40.00){\circle{2.00}}
\put(170.00,30.00){\circle{2.00}}
\put(170.00,20.00){\circle{2.00}}
\put(170.00,10.00){\circle*{2.00}}
\put(170.00,5.00){\makebox(0,0)[cc]{$p_1$}}
\put(170.00,11.00){\vector(0,1){8.00}}
\put(170.00,21.00){\vector(0,1){8.00}}
\put(170.00,31.00){\vector(0,1){8.00}}
\put(170.00,41.00){\vector(0,1){8.00}}
\put(170.00,51.00){\vector(0,1){8.00}}
\put(170.00,61.00){\vector(0,1){8.00}}
\put(170.00,71.00){\vector(0,1){8.00}}
\put(170.00,81.00){\vector(0,1){8.00}}
\put(180.00,70.00){\circle{2.00}}
\put(190.00,70.00){\circle{2.00}}
\put(180.00,80.00){\circle{2.00}}
\put(180.00,71.00){\vector(0,1){8.00}}
\put(180.00,90.00){\circle{2.00}}
\put(180.00,81.00){\vector(0,1){8.00}}
\put(190.00,80.00){\circle{2.00}}
\put(190.00,71.00){\vector(0,1){8.00}}
\put(190.00,90.00){\circle{2.00}}
\put(190.00,81.00){\vector(0,1){8.00}}
\put(150.00,50.00){\circle{2.00}}
\put(150.00,60.00){\circle{2.00}}
\put(150.00,51.00){\vector(0,1){8.00}}
\put(150.00,70.00){\circle{2.00}}
\put(150.00,61.00){\vector(0,1){8.00}}
\put(150.00,80.00){\circle{2.00}}
\put(150.00,71.00){\vector(0,1){8.00}}
\put(150.00,90.00){\circle{2.00}}
\put(150.00,81.00){\vector(0,1){8.00}}
\put(160.00,50.00){\circle{2.00}}
\put(160.00,60.00){\circle{2.00}}
\put(160.00,51.00){\vector(0,1){8.00}}
\put(160.00,70.00){\circle{2.00}}
\put(160.00,61.00){\vector(0,1){8.00}}
\put(160.00,80.00){\circle{2.00}}
\put(160.00,71.00){\vector(0,1){8.00}}
\put(160.00,90.00){\circle{2.00}}
\put(160.00,81.00){\vector(0,1){8.00}}
\put(168.67,39.67){\vector(-2,1){18.00}}
\put(169.00,40.33){\vector(-1,1){8.33}}
\put(170.67,60.33){\vector(1,1){8.67}}
\put(170.67,59.67){\vector(2,1){18.67}}
%\put(174.00,50.00){\makebox(0,0)[cc]{$s$}}
%\put(163.00,50.00){\makebox(0,0)[cc]{$s$}}
%\put(153.00,50.00){\makebox(0,0)[cc]{$s$}}
%\put(194.00,70.00){\makebox(0,0)[cc]{$t$}}
%\put(183.00,70.00){\makebox(0,0)[cc]{$t$}}
%\put(173.00,70.00){\makebox(0,0)[cc]{$t$}}
\end{picture}
\end{center}
\caption{In this flow diagram, the lowest ``root'' represents the
initial state of the computer. Forward computation represents
upwards motion
through a sequence of states represented by open circles. Different
symbols $p_i$ correspond to different initial computer states.
a) One-to-one computation.
b) Many-to-one junction which is information discarding. Several
computational paths, moving upwards, merge into one.
c) One-to-many computation is allowed only
 if no information is
created and discarded; e.g., in copy-type operations on blank memory.
From Landauer \protect\cite{landauer-94}.
\label{f-rev-comp}
}
\end{figure}
Classical
reversible computation
\cite{landauer:61,bennett-73,fred-tof-82,bennett-82,landauer-94}
is characterized by a single-valued invertible (i.e., bijective or
one-to-one) evolution function.
In such cases
it is always possible to ``reverse the gear'' of the evolution, and
compute the input from the output, the initial state from the final
state.

In irreversible computations, logical functions
are performed which
do not have a single-valued inverse, such as ${and}$ or ${or}$;
i.e., the input cannot be deduced from the output. Also deletion of
information or other many
(states)-to-one
(state) operations are irreversible.
This logical irreversibility is associated with physical irreversibility
and requires a minimal heat generation of the computing machine and
thus an entropy increase.




It is possible to embed any irreversible computation in an appropriate
environment which makes it reversible. For instance, the computer
could keep the inputs of previous calculations in successive order.
It could save all the information it would otherwise throw away.
 Or,
it could leave markers behind to identify its trail, the {\it H\"ansel
and Gretel} strategy described by Landauer \cite{landauer-94}. That, of
course, might amount to huge overheads in dynamical memory space
(and time) and would merely postpone the problem of throwing away
unwanted information. But, as has been pointed out by Bennett
\cite{bennett-73}, for classical computations, in which copying and
one-to-many operations are still allowed, this overhead could be
circumvented by
erasing all intermediate results, leaving behind only copies of the
output and the original input. Bennett's trick is
to perform  a computation,  copy the resulting output
and then, with one output as input, run
the computation backward. In order not to consume exceedingly large
intermediate storage resources, this strategy could be applied after
every single step.
Notice that copying can be done
reversible in classical physics if the memory used for the copy is
initially considered to be blank.

Quantum mechanics, in particular quantum computing, teaches us to
restrict ourselves even more and exclude any one-to-many operations, in
particular copying, and to accept merely one-to-one
computational operations
corresponding to bijective mappings [cf.
Figure \ref{f-rev-comp}a)].
This is due to the fact that the unitary
evolution of the quantum mechanical state state (between two subsequent
measurements) is strictly one-to-one.
Per definition, the inverse of a unitary operator $U$ representing a
quantum mechanical time evolution always exists. It is again a unitary
operator $U^{-1}=U^\dagger$ (where $\dagger$ represents the adjoint
operator); i.e., $UU^\dagger =1$.
As a consequence, the {\em no-cloning theorem}
\cite{herbert,wo-zu,mandel:83,mil-hard,glauber,caves}
states that certain one-to-many
operations are not allowed, in particular the copying of general
(nonclassical)
quantum bits of information.

In what follows we shall consider a particular example of a
one-to-one deterministic computation.  Although tentative in its present
form, this example may illustrate the conceptual strength of reversible
computation.  Our starting point are
finite automata \cite{e-f-moore,conway,brauer-84,schaller-96,cal-sv-yu},
but of a very particular,
hitherto unknown sort.  They are characterized by a finite set $S$ of
states, a finite input and output alphabet $I$ and $O$, respectively.
Like for Mealy automata, their temporal evolution and output functions
are given by $\delta :S\times I\rightarrow S$, $\lambda :S\times
I\rightarrow O$.  We additionally require one-to-one reversibility,
which we interpret in this context as follows.  Let $I=O$, and let the
combined (state and output) temporal evolution be associated with a
bijective map
\begin{equation}
U:(s,i)\rightarrow (\delta(s,i),\lambda (s,i)),
\label{t-e-l}
\end{equation}
with
$s\in S$ and $i\in I$.
The state and output symbol could be ``fed back'' consecutively; such
that
$N$ evolution steps correspond to $U^N=\underbrace{U\cdots U}_{N
\;\textrm{times}}$.

The elements of the Cartesian product
$S\times I$ can be arranged as a linear list of length
$n$ corresponding to  a vector. In this sense,
$U$ corresponds to a $n\times n$-matrix.  Let $\Psi_i$
be the $i$'th element in the vectorial representation of some
$(s,i)$, and let
$U_{ij}$ be the element
of
$U$ in the $i$'th row and the $j$'th column.
Due to
determinism, uniqueness and invertibility,
\begin{description}
\item[$\bullet$]
$U_{ij}\in \{0,1\}$;
\item[$\bullet$]
orthogonality:
 $U^{-1}=U^t$ (superscript $t$ means transposition) and
$(U^{-1})_{ij}=U_{ji}$;
\item[$\bullet$]
double stochasticity:
the sum of each row and column is one; i.e.,
$\sum_{i=1}^n U_{ij}= \sum_{j=1}^n U_{ij}=1$.
\end{description}
Since $U$ is a square matrix whose elements are either one or zero and
which has exactly one nonzero entry in each row and exactly one in each
column, it is a {\em permutation matrix}.
Let ${\cal P}_n$ denote the set of all $n\times n$ permutation matrices.
 ${\cal P}_n$ forms the {\em permutation group} (sometimes referred to
as the
{\em symmetric group}) of degree $n$. (The product of two permutation
matrices is
a permutation matrix, the inverse is the transpose and the identity
${\bf
1}$ belongs to  ${\cal P}_n$.)
${\cal P}_n$ has $n!$ elements.
Furthermore, the set of all doubly stochastic matrices forms a convex
polyhedron with the permutation matrices as vertices
\cite[page 82]{ber-ple}.

Let us be more specific.
For $n=1$, ${\cal P}_1=\{1\}$.\\
For $n=2$, ${\cal P}_2=\left\{
\left(
\begin{array}{cc}
1&0\\
0&1
\end{array}
\right)
,
\left(
\begin{array}{cc}
0&1\\
1&0
\end{array}
\right)
\right\}$.\\
For $n=3$,
\begin{eqnarray*}
{\cal P}_3&=&\left\{
\left(
\begin{array}{ccc}
1&0&0\\
0&1&0\\
0&0&1
\end{array}
\right)
,
\left(
\begin{array}{ccc}
1&0&0\\
0&0&1\\
0&1&0
\end{array}
\right)
,
\left(
\begin{array}{ccc}
0&1&0\\
0&0&1\\
1&0&0
\end{array}
\right)
\right. \hfill
,  \\
&&
\left.
\left(
\begin{array}{ccc}
0&1&0\\
1&0&0\\
0&0&1
\end{array}
\right)
,
\left(
\begin{array}{ccc}
0&0&1\\
1&0&0\\
0&1&0
\end{array}
\right)
,
\left(
\begin{array}{ccc}
0&0&1\\
0&1&0\\
1&0&0
\end{array}
\right)\right\}
.
\end{eqnarray*}

The correspondence between permutation matrices and
reversible automata is straightforward. Per definition [cf. Equation
(\ref{t-e-l})], every reversible automaton is representable by some
permutation matrix. That every $n\times n$ permutation matrix
corresponds to an automaton can be demonstrated by
considering the simplest
case of a one state automaton with $n$ input/output symbols.
There exist less trivial identifications. For example,
let $$  {U}=
\left(
\begin{array}{cccc}
0&0&1&0\\
0&1&0&0\\
0&0&0&1\\
1&0&0&0
\end{array}
\right).
$$
The transition and output functions of one associated reversible
automaton is listed in table
\ref{t-ra}.
\begin{table}
\begin{center}
\begin{tabular}{|c|cc|cc|}
 \hline
 \hline
 &$\delta$ & & $\lambda$&\\
$S\backslash I$ &1&2& 1&2\\
 \hline
$s_1$&$s_2$&$s_1$ & 1&2\\
$s_2$&$s_2$&$s_1 $& 2&1\\
 \hline
 \hline
\end{tabular}
\end{center}
\caption{Transition and output table of a reversible
automaton with two states $S=\{s_1, s_2\}$ and two input/output
symbols $I= \{1,2\}$.\label{t-ra}}
\end{table}
The associated flow diagram is drawn in Figure \ref{f-fdia}.
\begin{figure}
\begin{center}
%TexCad Options
%\grade{\off}
%\emlines{\off}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{4.05}
\unitlength 1.20mm
\linethickness{0.4pt}
\begin{picture}(30.75,15.75)
\put(0.00,5.00){\circle{1.50}}
\put(10.00,5.00){\circle{1.50}}
\put(20.00,5.00){\circle{1.50}}
\put(30.00,5.00){\circle{1.50}}
\put(0.00,15.00){\circle{1.50}}
\put(10.00,15.00){\circle{1.50}}
\put(20.00,15.00){\circle{1.50}}
\put(30.00,15.00){\circle{1.50}}
\put(0.00,0.00){\makebox(0,0)[cc]{$(s_1,1)$}}
\put(10.00,0.00){\makebox(0,0)[cc]{$(s_1,2)$}}
\put(20.00,0.00){\makebox(0,0)[cc]{$(s_2,1)$}}
\put(30.00,0.00){\makebox(0,0)[cc]{$(s_2,2)$}}
%\put(10.00,12.00){\vector(0,0){0.33}}
%\bezvec{88}(0.61,5.48)(11.63,7.70)(19.45,14.45)
\put(19.45,14.45){\vector(4,3){0.2}}
\multiput(0.61,5.48)(0.49,0.11){5}{\line(1,0){0.49}}
\multiput(3.07,6.05)(0.40,0.11){6}{\line(1,0){0.40}}
\multiput(5.45,6.73)(0.33,0.11){7}{\line(1,0){0.33}}
\multiput(7.75,7.52)(0.28,0.11){8}{\line(1,0){0.28}}
\multiput(9.97,8.44)(0.24,0.11){9}{\line(1,0){0.24}}
\multiput(12.10,9.47)(0.21,0.11){10}{\line(1,0){0.21}}
\multiput(14.15,10.62)(0.18,0.11){11}{\line(1,0){0.18}}
\multiput(16.12,11.88)(0.15,0.12){22}{\line(1,0){0.15}}
%\end
%\bezvec{32}(9.99,5.81)(9.99,13.96)(9.99,13.96)
\put(9.99,13.96){\vector(0,1){0.2}}
\put(9.99,5.81){\line(0,1){8.15}}
%\end
%\bezvec{124}(29.24,5.32)(8.51,7.21)(0.61,14.37)
\put(0.61,14.37){\vector(-4,3){0.2}}
\multiput(29.24,5.32)(-1.09,0.11){3}{\line(-1,0){1.09}}
\multiput(25.98,5.66)(-0.77,0.10){4}{\line(-1,0){0.77}}
\multiput(22.89,6.07)(-0.73,0.12){4}{\line(-1,0){0.73}}
\multiput(19.96,6.54)(-0.55,0.11){5}{\line(-1,0){0.55}}
\multiput(17.20,7.09)(-0.43,0.10){6}{\line(-1,0){0.43}}
\multiput(14.61,7.70)(-0.40,0.11){6}{\line(-1,0){0.40}}
\multiput(12.18,8.38)(-0.32,0.11){7}{\line(-1,0){0.32}}
\multiput(9.92,9.13)(-0.30,0.12){7}{\line(-1,0){0.30}}
\multiput(7.83,9.95)(-0.24,0.11){8}{\line(-1,0){0.24}}
\multiput(5.91,10.84)(-0.22,0.12){8}{\line(-1,0){0.22}}
\multiput(4.15,11.80)(-0.18,0.11){9}{\line(-1,0){0.18}}
\multiput(2.56,12.82)(-0.15,0.12){13}{\line(-1,0){0.15}}
%\end
%\bezvec{52}(20.44,5.73)(21.67,9.93)(29.49,14.37)
\put(29.49,14.37){\vector(3,2){0.2}}
\multiput(20.44,5.73)(0.12,0.27){6}{\line(0,1){0.27}}
\multiput(21.16,7.35)(0.11,0.15){11}{\line(0,1){0.15}}
\multiput(22.36,8.99)(0.12,0.12){14}{\line(1,0){0.12}}
\multiput(24.05,10.65)(0.16,0.12){14}{\line(1,0){0.16}}
\multiput(26.23,12.33)(0.19,0.12){17}{\line(1,0){0.19}}
%\end
\end{picture}
\end{center}
\caption{Flow diagram of one evolution cycle of the reversible automaton
listed in Table
\protect\ref{t-ra}.
\label{f-fdia}
}
\end{figure}
Since ${U}$ has a cycle 3; i.e., $({U})^3={\bf 1}$,
irrespective of the initial state, the automaton is back at its initial
state after three evolution steps. For example,
$
(s_1,1)\rightarrow
(s_2,1)\rightarrow
(s_2,2)\rightarrow
(s_1,1)$.

The discrete temporal evolution (\ref{t-e-l}) can, in matrix
notation, be represented by
\begin{equation}
U\Psi (N)= \Psi (N+1)=U^{N+1}\Psi (0),
\label{t-e-l2}
\end{equation}
where again $N=0,1,2,3,\ldots$ is a discrete time parameter.


%If we represent the elements of $S\times I$ as the vertex of a graph,
%$U$ can be interpreted as an adjacency matrix.
%Due to reversibility, there exist automata such that a cycle which
%includes every vertex of the graph, bringing the considerations close
%to Hamiltonian graphs \cite{brunner-pc}.


%\item[$\bullet$]
%\item[$\bullet$]
%\item[$\bullet$]
%\item[$\bullet$]
%\item[$\bullet$]
%\end{description}

Let us come back to our original issue of modelling the measurement
process within a system whose states evolve according  to a one-to-one
evolution.
Let us artificially divide such a system into an ``inside'' and an
``outside'' region.
This can be suitably represented by introducing a black box which
contains the ``inside'' region---the subsystem to be measured, whereas
the
remaining ``outside'' region is interpreted as the measurement
apparatus.
An input and an output interface mediate all interactions of the
``inside'' with the ``outside,'' of the ``observed'' and the
``observer'' by symbolic exchange. Let us assume that, despite such
symbolic exchanges via the interfaces
(for all practical purposes),
to an outside
observer
 what happens inside the black box is a hidden,
 inaccessible
  arena.
The observed system is like the ``black box'' drawn in
Figure~\ref{f-bbox}.
\begin{figure}
\begin{center}
%TexCad Options
%\grade{\off}
%\emlines{\off}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{1.00}
\unitlength 0.9mm
\linethickness{0.4pt}
\begin{picture}(79.33,115.00)
\put(2.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{1}$}}
\put(9.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{2}$}}
\put(16.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{3}$}}
\put(23.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{4}$}}
\put(30.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{5}$}}
\put(37.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{6}$}}
\put(44.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{7}$}}
\put(51.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{8}$}}
\put(58.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{9}$}}
\put(65.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{10}$}}
\put(72.33,14.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{11}$}}
\put(2.33,7.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{12}$}}
\put(9.33,7.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{13}$}}
\put(16.33,7.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{14}$}}
\put(23.33,7.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{15}$}}
\put(30.33,7.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{16}$}}
\put(37.33,7.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{17}$}}
\put(44.33,7.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{18}$}}
\put(51.33,7.67){\framebox(5.00,5.00)[cc]{$\footnotesize i_{19}$}}
\put(58.33,7.67){\framebox(5.00,5.00)[cc]{$\cdot$}}
\put(65.33,7.67){\framebox(5.00,5.00)[cc]{$\cdot$}}
\put(72.33,7.67){\framebox(5.00,5.00)[cc]{$\cdot$}}
\put(20.00,35.00){\line(1,0){30.00}}
\put(50.00,35.00){\line(0,1){25.00}}
\put(50.00,60.00){\line(-1,0){30.00}}
\put(20.00,60.00){\line(0,-1){25.00}}
\put(50.00,60.00){\line(3,2){15.00}}
\put(20.00,60.00){\line(3,2){15.00}}
\put(50.00,35.00){\line(3,2){15.00}}
\put(65.00,45.00){\line(0,1){25.00}}
\put(65.00,70.00){\line(-1,0){30.00}}
\put(0.00,5.00){\line(1,0){79.33}}
\put(79.33,5.00){\line(0,1){17.00}}
\put(79.33,22.00){\line(-1,0){79.33}}
\put(0.00,22.00){\line(0,-1){17.00}}
\put(30.00,90.00){\line(1,0){20.00}}
\put(50.00,90.00){\line(0,1){20.00}}
\put(50.00,110.00){\line(-1,0){20.00}}
\put(30.00,110.00){\line(0,-1){20.00}}
%\bezier{100}(40.67,66.33)(50.00,79.33)(41.00,78.67)
\multiput(40.67,66.33)(0.11,0.16){15}{\line(0,1){0.16}}
\multiput(42.35,68.80)(0.12,0.20){11}{\line(0,1){0.20}}
\multiput(43.67,70.99)(0.12,0.24){8}{\line(0,1){0.24}}
\multiput(44.62,72.90)(0.12,0.33){5}{\line(0,1){0.33}}
\multiput(45.20,74.55)(0.11,0.69){2}{\line(0,1){0.69}}
\multiput(45.42,75.92)(-0.08,0.55){2}{\line(0,1){0.55}}
\multiput(45.27,77.01)(-0.10,0.16){5}{\line(0,1){0.16}}
\multiput(44.75,77.84)(-0.18,0.11){5}{\line(-1,0){0.18}}
\multiput(43.87,78.39)(-0.42,0.09){3}{\line(-1,0){0.42}}
\put(42.62,78.66){\line(-1,0){1.62}}
%\end
%\bezier{108}(41.00,78.67)(30.00,78.33)(40.33,90.00)
\put(41.00,78.67){\line(-1,0){1.85}}
\multiput(39.15,78.71)(-0.50,0.08){3}{\line(-1,0){0.50}}
\multiput(37.66,78.95)(-0.28,0.11){4}{\line(-1,0){0.28}}
\multiput(36.53,79.41)(-0.13,0.11){6}{\line(-1,0){0.13}}
\multiput(35.78,80.07)(-0.10,0.22){4}{\line(0,1){0.22}}
\put(35.39,80.93){\line(0,1){1.07}}
\multiput(35.36,82.00)(0.11,0.43){3}{\line(0,1){0.43}}
\multiput(35.70,83.28)(0.12,0.25){6}{\line(0,1){0.25}}
\multiput(36.41,84.76)(0.12,0.19){9}{\line(0,1){0.19}}
\multiput(37.48,86.44)(0.12,0.15){24}{\line(0,1){0.15}}
%\end
%\bezier{56}(39.67,34.67)(45.33,32.00)(39.00,28.00)
\multiput(39.67,34.67)(0.18,-0.11){9}{\line(1,0){0.18}}
\multiput(41.31,33.67)(0.11,-0.13){8}{\line(0,-1){0.13}}
\put(42.18,32.59){\line(0,-1){1.16}}
\multiput(42.29,31.43)(-0.11,-0.21){6}{\line(0,-1){0.21}}
\multiput(41.64,30.18)(-0.14,-0.11){19}{\line(-1,0){0.14}}
%\end
%\bezier{52}(39.00,28.00)(33.33,25.67)(38.67,22.00)
\multiput(39.00,28.00)(-0.22,-0.12){8}{\line(-1,0){0.22}}
\multiput(37.23,27.05)(-0.12,-0.13){8}{\line(0,-1){0.13}}
\multiput(36.27,26.01)(-0.07,-0.57){2}{\line(0,-1){0.57}}
\multiput(36.12,24.86)(0.11,-0.21){6}{\line(0,-1){0.21}}
\multiput(36.79,23.62)(0.13,-0.12){14}{\line(1,0){0.13}}
%\end
\put(35.00,47.33){\makebox(0,0)[cc]{\huge ?}}
\put(40.00,100.00){\makebox(0,0)[cc]{$o_j$}}
\put(40.00,0.00){\makebox(0,0)[cc]{input interface}}
\put(40.00,115.00){\makebox(0,0)[cc]{output interface}}
\put(70.00,55.00){\makebox(0,0)[lc]{box}}
\end{picture}
\end{center}
\caption{\label{f-bbox}
A system in a black box
with an input interface and an output interface.}
\end{figure}


Throughout temporal evolution, not only is information transformed
one-to-one
(bijectively, homomorphically) inside the black box,
but
this information is handled  one-to-one {\em after} it appeared on the
black box
interfaces. It might  seem evident at first glance that the symbols
appearing on the interfaces should be treated as classical information.
That is, they could in principle be copied. The possibility to copy the
experiment (input and output) enables the application of Bennett's
argument: in such a case, one keeps the experimental finding by copying
it, reverts the system evolution and starts with a ``fresh'' black
box system in its original initial state. The result is a
classical Boolean calculus.

The scenario is drastically changed, however, if we assume a
one-to-one evolution also for the environment at and outside
of the black box. That is, one deals with a
homogeneous
and uniform one-to-one evolution ``inside'' and ``outside'' of the black
box, thereby
assuming that the experimenter also evolves
one-to-one and not classically.
In our toy automaton model, this could for instance be realized by some
automaton corresponding to a permutation operator $U$ inside the black
box, and another reversible automaton corresponding to another $U'$
outside of it. Conventionally, $U$ and $U'$ correspond to the measured
system and the measurement device, respectively.

In such a case, as there is no copying due to one-to-one evolution,
in order to set
back the system to its original initial state, the experimenter would
have to erase all knowledge bits of information acquired so far.
The experiment would have to evolve back to the initial state of the
measurement device and the measured system prior to the measurement.
As a result, the representation of measurement results in one-to-one
reversible systems may cause a sort of complementarity due to
the impossibility to measure all variants of the representation
at once.

Let us give a brief example. Consider the $6\times 6$ permutation matrix
$$
U=
\left(
\begin{array}{cccccc}
0&1&0&0&0&0\\
0&0&0&0&0&1\\
0&0&1&0&0&0\\
1&0&0&0&0&0\\
0&0&0&0&1&0\\
0&0&0&1&0&0
\end{array}
\right)
$$
corresponding to a reversible $3$-state automaton with two input/output
symbols $1,2$
listed in table
\ref{t-rra}.
\begin{table}
\begin{center}
\begin{tabular}{|c|cc|cc|}
 \hline
 \hline
 &$\delta$ & & $\lambda$&\\
$S\backslash I$ &1&2& 1&2\\
 \hline
$s_1$&$s_1$&$s_3$ & 2&2\\
$s_2$&$s_2$&$s_1 $& 1&1\\
$s_3$&$s_3$&$s_2 $& 1&2\\
 \hline
 \hline
\end{tabular}
\end{center}
\caption{Transition and output table of a reversible
automaton with three states $S=\{s_1, s_2, s_3\}$ and two input/output
symbols $I= \{1,2\}$.\label{t-rra}}
\end{table}
The evolution is
$$
\left(
\begin{array}{c}
(s_1,1)                \\
(s_1,2)                \\
(s_2,1)                \\
(s_2,2)                \\
(s_3,1)                \\
(s_3,2)
\end{array}
\right)
\stackrel{U}{\longrightarrow }
\left(
\begin{array}{c}
(s_1,2)                \\
(s_3,2)                \\
(s_2,1)                \\
(s_1,1)                \\
(s_3,1)                \\
(s_2,2)
\end{array}
\right)
\stackrel{U}{\longrightarrow }
\left(
\begin{array}{c}
(s_3,2)                \\
(s_2,2)                \\
(s_2,1)                \\
(s_1,2)                \\
(s_3,1)                \\
(s_1,1)
\end{array}
\right)
\stackrel{U}{\longrightarrow }
\left(
\begin{array}{c}
(s_2,2)                \\
(s_1,1)                \\
(s_2,1)                \\
(s_3,2)                \\
(s_3,1)                \\
(s_1,2)
\end{array}
\right)
\stackrel{U}{\longrightarrow }
\left(
\begin{array}{c}
(s_1,1)                \\
(s_1,2)                \\
(s_2,1)                \\
(s_2,2)                \\
(s_3,1)                \\
(s_3,2)
\end{array}
\right).
  $$
The associated flow diagram is drawn in Figure \ref{f-ffdia}.
\begin{figure}
\begin{center}
%TexCad Options
%\grade{\off}
%\emlines{\off}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{1.90}
\unitlength 1.20mm
\linethickness{0.4pt}
\begin{picture}(50.75,45.80)
\put(0.00,5.00){\circle{1.50}}
\put(10.00,5.00){\circle{1.50}}
\put(20.00,5.00){\circle{1.50}}
\put(30.00,5.00){\circle{1.50}}
\put(0.00,15.00){\circle{1.50}}
\put(10.00,15.00){\circle{1.50}}
\put(20.00,15.00){\circle{1.50}}
\put(30.00,15.00){\circle{1.50}}
\put(0.00,0.00){\makebox(0,0)[cc]{ $(s_1,1)$}}
\put(10.00,0.00){\makebox(0,0)[cc]{ $(s_1,2)$}}
\put(20.00,0.00){\makebox(0,0)[cc]{ $(s_2,1)$}}
\put(30.00,0.00){\makebox(0,0)[cc]{ $(s_2,2)$}}
\put(40.00,5.00){\circle{1.50}}
\put(50.00,5.00){\circle{1.50}}
\put(40.00,15.00){\circle{1.50}}
\put(50.00,15.00){\circle{1.50}}
\put(40.00,0.00){\makebox(0,0)[cc]{ $(s_3,1)$}}
\put(50.00,0.00){\makebox(0,0)[cc]{ $(s_3,2)$}}
\put(20.00,6.00){\vector(0,1){8.00}}
\put(40.00,6.00){\vector(0,1){8.00}}
%\bezvec{48}(1.05,6.00)(3.16,11.10)(8.96,14.09)
\put(8.96,14.09){\vector(3,2){0.2}}
\multiput(1.05,6.00)(0.12,0.23){9}{\line(0,1){0.23}}
\multiput(2.09,8.03)(0.11,0.15){12}{\line(0,1){0.15}}
\multiput(3.45,9.88)(0.12,0.12){14}{\line(1,0){0.12}}
\multiput(5.13,11.55)(0.17,0.12){22}{\line(1,0){0.17}}
%\end
%\bezvec{160}(11.07,6.00)(14.23,10.04)(49.03,14.09)
\put(49.03,14.09){\vector(1,0){0.2}}
\multiput(11.07,6.00)(0.10,0.10){5}{\line(1,0){0.10}}
\multiput(11.59,6.51)(0.15,0.10){5}{\line(1,0){0.15}}
\multiput(12.35,7.01)(0.20,0.10){5}{\line(1,0){0.20}}
\multiput(13.37,7.52)(0.25,0.10){5}{\line(1,0){0.25}}
\multiput(14.63,8.02)(0.30,0.10){5}{\line(1,0){0.30}}
\multiput(16.14,8.53)(0.35,0.10){5}{\line(1,0){0.35}}
\multiput(17.89,9.03)(0.40,0.10){5}{\line(1,0){0.40}}
\multiput(19.89,9.54)(0.45,0.10){5}{\line(1,0){0.45}}
\multiput(22.14,10.04)(0.50,0.10){5}{\line(1,0){0.50}}
\multiput(24.64,10.55)(0.55,0.10){5}{\line(1,0){0.55}}
\multiput(27.38,11.06)(0.60,0.10){5}{\line(1,0){0.60}}
\multiput(30.37,11.56)(0.65,0.10){5}{\line(1,0){0.65}}
\multiput(33.61,12.07)(0.80,0.11){9}{\line(1,0){0.80}}
\multiput(40.82,13.08)(0.91,0.11){9}{\line(1,0){0.91}}
%\end
%\bezvec{132}(28.99,6.00)(1.23,9.34)(1.05,14.09)
\put(1.05,14.09){\vector(-1,4){0.2}}
\multiput(28.99,6.00)(-0.81,0.10){5}{\line(-1,0){0.81}}
\multiput(24.95,6.52)(-0.75,0.11){5}{\line(-1,0){0.75}}
\multiput(21.21,7.05)(-0.68,0.11){5}{\line(-1,0){0.68}}
\multiput(17.80,7.59)(-0.62,0.11){5}{\line(-1,0){0.62}}
\multiput(14.70,8.16)(-0.56,0.12){5}{\line(-1,0){0.56}}
\multiput(11.92,8.73)(-0.49,0.12){5}{\line(-1,0){0.49}}
\multiput(9.45,9.33)(-0.36,0.10){6}{\line(-1,0){0.36}}
\multiput(7.30,9.94)(-0.31,0.10){6}{\line(-1,0){0.31}}
\multiput(5.47,10.57)(-0.25,0.11){6}{\line(-1,0){0.25}}
\multiput(3.96,11.21)(-0.20,0.11){6}{\line(-1,0){0.20}}
\multiput(2.76,11.87)(-0.15,0.11){6}{\line(-1,0){0.15}}
\multiput(1.88,12.54)(-0.11,0.14){5}{\line(0,1){0.14}}
\multiput(1.31,13.24)(-0.09,0.28){3}{\line(0,1){0.28}}
%\end
%\bezvec{84}(49.03,6.00)(42.70,12.50)(30.93,14.09)
\put(30.93,14.09){\vector(-4,1){0.2}}
\multiput(49.03,6.00)(-0.12,0.11){13}{\line(-1,0){0.12}}
\multiput(47.44,7.48)(-0.14,0.11){12}{\line(-1,0){0.14}}
\multiput(45.71,8.82)(-0.19,0.12){10}{\line(-1,0){0.19}}
\multiput(43.81,10.02)(-0.23,0.12){9}{\line(-1,0){0.23}}
\multiput(41.77,11.08)(-0.28,0.12){8}{\line(-1,0){0.28}}
\multiput(39.57,12.00)(-0.34,0.11){7}{\line(-1,0){0.34}}
\multiput(37.21,12.78)(-0.42,0.11){6}{\line(-1,0){0.42}}
\multiput(34.70,13.42)(-0.63,0.11){6}{\line(-1,0){0.63}}
%\end
\put(0.00,25.02){\circle{1.50}}
\put(0.00,35.03){\circle{1.50}}
\put(0.00,45.05){\circle{1.50}}
\put(10.00,25.02){\circle{1.50}}
\put(10.00,35.03){\circle{1.50}}
\put(10.00,45.05){\circle{1.50}}
\put(20.00,25.02){\circle{1.50}}
\put(20.00,35.03){\circle{1.50}}
\put(20.00,45.05){\circle{1.50}}
\put(30.00,25.02){\circle{1.50}}
\put(30.00,35.03){\circle{1.50}}
\put(30.00,45.05){\circle{1.50}}
\put(40.00,25.02){\circle{1.50}}
\put(40.00,35.03){\circle{1.50}}
\put(40.00,45.05){\circle{1.50}}
\put(50.00,25.02){\circle{1.50}}
\put(50.00,35.03){\circle{1.50}}
\put(50.00,45.05){\circle{1.50}}
\put(20.00,16.02){\vector(0,1){8.00}}
\put(20.00,26.03){\vector(0,1){8.00}}
\put(20.00,36.05){\vector(0,1){8.00}}
\put(40.00,16.02){\vector(0,1){8.00}}
\put(40.00,26.03){\vector(0,1){8.00}}
\put(40.00,36.05){\vector(0,1){8.00}}
%\bezvec{48}(1.05,16.02)(3.16,21.12)(8.96,24.10)
\put(8.96,24.10){\vector(3,2){0.2}}
\multiput(1.05,16.02)(0.12,0.23){9}{\line(0,1){0.23}}
\multiput(2.09,18.05)(0.11,0.15){12}{\line(0,1){0.15}}
\multiput(3.45,19.90)(0.12,0.12){14}{\line(1,0){0.12}}
\multiput(5.13,21.57)(0.17,0.12){22}{\line(1,0){0.17}}
%\end
%\bezvec{48}(1.05,26.04)(3.16,31.13)(8.96,34.12)
\put(8.96,34.12){\vector(3,2){0.2}}
\multiput(1.05,26.04)(0.12,0.23){9}{\line(0,1){0.23}}
\multiput(2.09,28.07)(0.11,0.15){12}{\line(0,1){0.15}}
\multiput(3.45,29.92)(0.12,0.12){14}{\line(1,0){0.12}}
\multiput(5.13,31.58)(0.17,0.12){22}{\line(1,0){0.17}}
%\end
%\bezvec{48}(1.05,36.05)(3.16,41.15)(8.96,44.14)
\put(8.96,44.14){\vector(3,2){0.2}}
\multiput(1.05,36.05)(0.12,0.23){9}{\line(0,1){0.23}}
\multiput(2.09,38.08)(0.11,0.15){12}{\line(0,1){0.15}}
\multiput(3.45,39.93)(0.12,0.12){14}{\line(1,0){0.12}}
\multiput(5.13,41.60)(0.17,0.12){22}{\line(1,0){0.17}}
%\end
%\bezvec{160}(11.07,16.02)(14.23,20.06)(49.03,24.10)
\put(49.03,24.10){\vector(1,0){0.2}}
\multiput(11.07,16.02)(0.10,0.10){5}{\line(1,0){0.10}}
\multiput(11.59,16.52)(0.15,0.10){5}{\line(1,0){0.15}}
\multiput(12.35,17.03)(0.20,0.10){5}{\line(1,0){0.20}}
\multiput(13.37,17.54)(0.25,0.10){5}{\line(1,0){0.25}}
\multiput(14.63,18.04)(0.30,0.10){5}{\line(1,0){0.30}}
\multiput(16.14,18.55)(0.35,0.10){5}{\line(1,0){0.35}}
\multiput(17.89,19.05)(0.40,0.10){5}{\line(1,0){0.40}}
\multiput(19.89,19.56)(0.45,0.10){5}{\line(1,0){0.45}}
\multiput(22.14,20.06)(0.50,0.10){5}{\line(1,0){0.50}}
\multiput(24.64,20.57)(0.55,0.10){5}{\line(1,0){0.55}}
\multiput(27.38,21.07)(0.60,0.10){5}{\line(1,0){0.60}}
\multiput(30.37,21.58)(0.65,0.10){5}{\line(1,0){0.65}}
\multiput(33.61,22.08)(0.80,0.11){9}{\line(1,0){0.80}}
\multiput(40.82,23.09)(0.91,0.11){9}{\line(1,0){0.91}}
%\end
%\bezvec{160}(11.07,26.04)(14.23,30.08)(49.03,34.12)
\put(49.03,34.12){\vector(1,0){0.2}}
\multiput(11.07,26.04)(0.10,0.10){5}{\line(1,0){0.10}}
\multiput(11.59,26.54)(0.15,0.10){5}{\line(1,0){0.15}}
\multiput(12.35,27.05)(0.20,0.10){5}{\line(1,0){0.20}}
\multiput(13.37,27.55)(0.25,0.10){5}{\line(1,0){0.25}}
\multiput(14.63,28.06)(0.30,0.10){5}{\line(1,0){0.30}}
\multiput(16.14,28.56)(0.35,0.10){5}{\line(1,0){0.35}}
\multiput(17.89,29.07)(0.40,0.10){5}{\line(1,0){0.40}}
\multiput(19.89,29.57)(0.45,0.10){5}{\line(1,0){0.45}}
\multiput(22.14,30.08)(0.50,0.10){5}{\line(1,0){0.50}}
\multiput(24.64,30.58)(0.55,0.10){5}{\line(1,0){0.55}}
\multiput(27.38,31.09)(0.60,0.10){5}{\line(1,0){0.60}}
\multiput(30.37,31.59)(0.65,0.10){5}{\line(1,0){0.65}}
\multiput(33.61,32.10)(0.80,0.11){9}{\line(1,0){0.80}}
\multiput(40.82,33.11)(0.91,0.11){9}{\line(1,0){0.91}}
%\end
%\bezvec{160}(11.07,36.05)(14.23,40.09)(49.03,44.14)
\put(49.03,44.14){\vector(1,0){0.2}}
\multiput(11.07,36.05)(0.10,0.10){5}{\line(1,0){0.10}}
\multiput(11.59,36.56)(0.15,0.10){5}{\line(1,0){0.15}}
\multiput(12.35,37.06)(0.20,0.10){5}{\line(1,0){0.20}}
\multiput(13.37,37.57)(0.25,0.10){5}{\line(1,0){0.25}}
\multiput(14.63,38.07)(0.30,0.10){5}{\line(1,0){0.30}}
\multiput(16.14,38.58)(0.35,0.10){5}{\line(1,0){0.35}}
\multiput(17.89,39.08)(0.40,0.10){5}{\line(1,0){0.40}}
\multiput(19.89,39.59)(0.45,0.10){5}{\line(1,0){0.45}}
\multiput(22.14,40.09)(0.50,0.10){5}{\line(1,0){0.50}}
\multiput(24.64,40.60)(0.55,0.10){5}{\line(1,0){0.55}}
\multiput(27.38,41.11)(0.60,0.10){5}{\line(1,0){0.60}}
\multiput(30.37,41.61)(0.65,0.10){5}{\line(1,0){0.65}}
\multiput(33.61,42.12)(0.80,0.11){9}{\line(1,0){0.80}}
\multiput(40.82,43.13)(0.91,0.11){9}{\line(1,0){0.91}}
%\end
%\bezvec{132}(28.99,16.02)(1.23,19.36)(1.05,24.10)
\put(1.05,24.10){\vector(-1,4){0.2}}
\multiput(28.99,16.02)(-0.81,0.10){5}{\line(-1,0){0.81}}
\multiput(24.95,16.53)(-0.75,0.11){5}{\line(-1,0){0.75}}
\multiput(21.21,17.06)(-0.68,0.11){5}{\line(-1,0){0.68}}
\multiput(17.80,17.61)(-0.62,0.11){5}{\line(-1,0){0.62}}
\multiput(14.70,18.17)(-0.56,0.12){5}{\line(-1,0){0.56}}
\multiput(11.92,18.75)(-0.49,0.12){5}{\line(-1,0){0.49}}
\multiput(9.45,19.35)(-0.36,0.10){6}{\line(-1,0){0.36}}
\multiput(7.30,19.96)(-0.31,0.10){6}{\line(-1,0){0.31}}
\multiput(5.47,20.58)(-0.25,0.11){6}{\line(-1,0){0.25}}
\multiput(3.96,21.23)(-0.20,0.11){6}{\line(-1,0){0.20}}
\multiput(2.76,21.89)(-0.15,0.11){6}{\line(-1,0){0.15}}
\multiput(1.88,22.56)(-0.11,0.14){5}{\line(0,1){0.14}}
\multiput(1.31,23.25)(-0.09,0.28){3}{\line(0,1){0.28}}
%\end
%\bezvec{132}(28.99,26.04)(1.23,29.38)(1.05,34.12)
\put(1.05,34.12){\vector(-1,4){0.2}}
\multiput(28.99,26.04)(-0.81,0.10){5}{\line(-1,0){0.81}}
\multiput(24.95,26.55)(-0.75,0.11){5}{\line(-1,0){0.75}}
\multiput(21.21,27.08)(-0.68,0.11){5}{\line(-1,0){0.68}}
\multiput(17.80,27.63)(-0.62,0.11){5}{\line(-1,0){0.62}}
\multiput(14.70,28.19)(-0.56,0.12){5}{\line(-1,0){0.56}}
\multiput(11.92,28.77)(-0.49,0.12){5}{\line(-1,0){0.49}}
\multiput(9.45,29.36)(-0.36,0.10){6}{\line(-1,0){0.36}}
\multiput(7.30,29.97)(-0.31,0.10){6}{\line(-1,0){0.31}}
\multiput(5.47,30.60)(-0.25,0.11){6}{\line(-1,0){0.25}}
\multiput(3.96,31.24)(-0.20,0.11){6}{\line(-1,0){0.20}}
\multiput(2.76,31.90)(-0.15,0.11){6}{\line(-1,0){0.15}}
\multiput(1.88,32.58)(-0.11,0.14){5}{\line(0,1){0.14}}
\multiput(1.31,33.27)(-0.09,0.28){3}{\line(0,1){0.28}}
%\end
%\bezvec{132}(28.99,36.05)(1.23,39.39)(1.05,44.14)
\put(1.05,44.14){\vector(-1,4){0.2}}
\multiput(28.99,36.05)(-0.81,0.10){5}{\line(-1,0){0.81}}
\multiput(24.95,36.57)(-0.75,0.11){5}{\line(-1,0){0.75}}
\multiput(21.21,37.10)(-0.68,0.11){5}{\line(-1,0){0.68}}
\multiput(17.80,37.64)(-0.62,0.11){5}{\line(-1,0){0.62}}
\multiput(14.70,38.21)(-0.56,0.12){5}{\line(-1,0){0.56}}
\multiput(11.92,38.78)(-0.49,0.12){5}{\line(-1,0){0.49}}
\multiput(9.45,39.38)(-0.36,0.10){6}{\line(-1,0){0.36}}
\multiput(7.30,39.99)(-0.31,0.10){6}{\line(-1,0){0.31}}
\multiput(5.47,40.62)(-0.25,0.11){6}{\line(-1,0){0.25}}
\multiput(3.96,41.26)(-0.20,0.11){6}{\line(-1,0){0.20}}
\multiput(2.76,41.92)(-0.15,0.11){6}{\line(-1,0){0.15}}
\multiput(1.88,42.59)(-0.11,0.14){5}{\line(0,1){0.14}}
\multiput(1.31,43.29)(-0.09,0.28){3}{\line(0,1){0.28}}
%\end
%\bezvec{84}(49.03,16.02)(42.70,22.52)(30.93,24.10)
\put(30.93,24.10){\vector(-4,1){0.2}}
\multiput(49.03,16.02)(-0.12,0.11){13}{\line(-1,0){0.12}}
\multiput(47.44,17.50)(-0.14,0.11){12}{\line(-1,0){0.14}}
\multiput(45.71,18.84)(-0.19,0.12){10}{\line(-1,0){0.19}}
\multiput(43.81,20.04)(-0.23,0.12){9}{\line(-1,0){0.23}}
\multiput(41.77,21.10)(-0.28,0.12){8}{\line(-1,0){0.28}}
\multiput(39.57,22.02)(-0.34,0.11){7}{\line(-1,0){0.34}}
\multiput(37.21,22.80)(-0.42,0.11){6}{\line(-1,0){0.42}}
\multiput(34.70,23.44)(-0.63,0.11){6}{\line(-1,0){0.63}}
%\end
%\bezvec{84}(49.03,26.04)(42.70,32.54)(30.93,34.12)
\put(30.93,34.12){\vector(-4,1){0.2}}
\multiput(49.03,26.04)(-0.12,0.11){13}{\line(-1,0){0.12}}
\multiput(47.44,27.51)(-0.14,0.11){12}{\line(-1,0){0.14}}
\multiput(45.71,28.85)(-0.19,0.12){10}{\line(-1,0){0.19}}
\multiput(43.81,30.05)(-0.23,0.12){9}{\line(-1,0){0.23}}
\multiput(41.77,31.11)(-0.28,0.12){8}{\line(-1,0){0.28}}
\multiput(39.57,32.03)(-0.34,0.11){7}{\line(-1,0){0.34}}
\multiput(37.21,32.81)(-0.42,0.11){6}{\line(-1,0){0.42}}
\multiput(34.70,33.46)(-0.63,0.11){6}{\line(-1,0){0.63}}
%\end
%\bezvec{84}(49.03,36.05)(42.70,42.56)(30.93,44.14)
\put(30.93,44.14){\vector(-4,1){0.2}}
\multiput(49.03,36.05)(-0.12,0.11){13}{\line(-1,0){0.12}}
\multiput(47.44,37.53)(-0.14,0.11){12}{\line(-1,0){0.14}}
\multiput(45.71,38.87)(-0.19,0.12){10}{\line(-1,0){0.19}}
\multiput(43.81,40.07)(-0.23,0.12){9}{\line(-1,0){0.23}}
\multiput(41.77,41.13)(-0.28,0.12){8}{\line(-1,0){0.28}}
\multiput(39.57,42.05)(-0.34,0.11){7}{\line(-1,0){0.34}}
\multiput(37.21,42.83)(-0.42,0.11){6}{\line(-1,0){0.42}}
\multiput(34.70,43.47)(-0.63,0.11){6}{\line(-1,0){0.63}}
%\end
\end{picture}
\end{center}
\caption{Flow diagram of four evolution cycles of the reversible
automaton listed in Table
\protect\ref{t-rra}.
\label{f-ffdia}
}
\end{figure}
Thus after the input of just one symbol, the automaton states can be
grouped into experimental equivalence classes \cite{svozil-93}
$$v(1)=\{\{1\},\{2,3\}\},\quad
v(2)=\{\{1,3\},\{2\}\}.$$
The associated partition logic corresponds to a non Boolean
(nondistributive)
partition logic isomorphic to $MO_2$. Of course, if one develops the
automaton further, then, for instance, $v(2222)=\{\{1\},\{2\},\{3\}\}$,
and the classical case is recovered [notice that this is not the case
for $v(\stackrel{\cdot}{1})=v(1)$]. Yet, if one assumes that the output
is channelled away
into the interface after only a single evolution step (and
that afterwards the evolution is via another $U'$), the
nonclassical feature pertains despite the bijective character of the
evolution.

In this epistemic model, the interface symbolizes the {\em cut} between
the observer and the observed. The cut appears somewhat arbitrary in a
computational universe which is assumed to be uniformly reversible.

What has been discussed above is very similar to the
opening,
closing and reopening of Schr\"odinger's catalogue of expectation values
\cite[p. 53]{schrodinger}:
At least up to
a certain magnitude of complexity---any measurement can be ``undone'' by
a proper reconstruction of the wave-function. A necessary condition for
this to happen is that {\em all} information about the original
measurement is lost.
In Schr\"odinger's terms,
the prediction catalog
(the wave function) can be opened only at one particular page.
We may close
the prediction catalog
before reading this page. Then we can open
the prediction catalog
at another, complementary, page again.
By no way we can open
the prediction catalog at one page, read and (irreversible) memorize the
page, close it; then open it at another, complementary, page.
(Two noncomplementary pages which correspond to two co-measurable
observables can be read simultaneously.)



From this point of view, it appears that, strictly speaking,
irreversibility
may turn out to be an inappropriate concept both in computational
universes generated by one-to-one evolution as well as for quantum
measurement theory. Indeed, irreversibility may have been imposed upon
the measurement process
rather heuristically and artificially to express the huge practical
difficulties associated with any
backward evolution, with ``reversing the gear'', or with reconstructing
a coherent state.
 To quote Landauer
\cite[section 2]{landauer-89},
 \begin{quote}
{\em ``What is measurement? If it is simply information transfer, that
is done all the time inside the computer, and can be done with arbitrary
little dissipation.''}
 \end{quote}

Let us conclude with a metaphysical speculation.
In a one-to-one invertible universe, any  evolution, any step of
computation, any single measurement
act reminds us of a permanent permutation, reformulation and reiteration
of one
and the same ``message''---a ``message'' that was there already at the
beginning of the universe, which gets transformed but is neither
destroyed nor renewed. This thought might be very close to what
Schr\"odinger had in mind when contemplating about Vedic philosophy
\cite{schroed:welt}.




%\bibliography{svozil}
%%\bibliographystyle{plain}
%\bibliographystyle{acm}

\begin{thebibliography}{10}

\bibitem{benna:62}
{\sc Benacerraf, P.}
\newblock Tasks and supertasks, and the modern {E}leatics.
\newblock {\em Journal of Philosophy LIX}, 24 (1962), 765--784.

\bibitem{bennett-73}
{\sc Bennett, C.~H.}
\newblock Logical reversibility of computation.
\newblock {\em IBM Journal of Research and Development 17\/} (1973), 525--532.
\newblock Reprinted in \cite[pp. 197-204]{maxwell-demon}.

\bibitem{bennett-82}
{\sc Bennett, C.~H.}
\newblock The thermodynamics of computation---a review.
\newblock In {\em International Journal of Theoretical Physics\/}
  \cite{maxwell-demon}, pp.~905--940.
\newblock Reprinted in \cite[pp. 213-248]{maxwell-demon}.

\bibitem{ber-ple}
{\sc Berman, A., and Plemmons, R.~J.}
\newblock {\em Nonnegative Matrices in the Mathematical Sciences}.
\newblock Academic Press, New York, 1979.

\bibitem{beth-59}
{\sc Beth, E.~W.}
\newblock {\em The Foundations of Metamathematics}.
\newblock North-Holland, Amsterdam, 1959.

\bibitem{brauer-84}
{\sc Brauer, W.}
\newblock {\em Automatentheorie}.
\newblock Teubner, Stuttgart, 1984.

\bibitem{brillouin1}
{\sc Brillouin, L.}
\newblock {\em Science and Information}, second edition~ed.
\newblock Academic Press, New York, 1962.

\bibitem{brillouin2}
{\sc Brillouin, L.}
\newblock {\em Scientific Uncertainty and Information}.
\newblock Academic Press, New York, 1964.

\bibitem{calude:94}
{\sc Calude, C.}
\newblock {\em Information and Randomness---An Algorithmic Perspective}.
\newblock Springer, Berlin, 1994.

\bibitem{cal-sv-yu}
{\sc Calude, C., Calude, E., Svozil, K., and Yu, S.}
\newblock Physical versus computational complementarity {I}.
\newblock {\em International Journal of Theoretical Physics 36}, 7 (1997),
  1495--1523.

\bibitem{caves}
{\sc Caves, C.~M.}
\newblock Quantum limits on noise in linear amplifiers.
\newblock {\em Physical Review D26\/} (1982), 1817--1839.

\bibitem{chaitin:92}
{\sc Chaitin, G.~J.}
\newblock {\em Information-Theoretic Incompleteness}.
\newblock World Scientific, Singapore, 1992.

\bibitem{conway}
{\sc Conway, J.~H.}
\newblock {\em Regular Algebra and Finite Machines}.
\newblock Chapman and Hall Ltd., London, 1971.

\bibitem{davis-58}
{\sc Davis, M.}
\newblock {\em Computability and Unsolvability}.
\newblock McGraw-Hill, New York, 1958.

\bibitem{deutsch}
{\sc Deutsch, D.}
\newblock Quantum theory, the {C}hurch-{T}uring principle and the universal
  quantum computer.
\newblock {\em Proceedings of the Royal Society London A 400\/} (1985),
  97--119.

\bibitem{ear-nor:93}
{\sc Earman, J., and Norton, J.~D.}
\newblock Forever is a day: supertasks in {P}itowsky and {M}alament-{H}ogart
  spacetimes.
\newblock {\em Philosophy of Science 60\/} (1993), 22--42.

\bibitem{ekerj96}
{\sc Ekert, A., and Jozsa, R.}
\newblock Quantum computation and {S}hor's factoring algorithm.
\newblock {\em Reviews of Modern Physics 68}, 3 (1996), 733--753.

\bibitem{scilard-col}
{\sc Feld, B.~T., and Szilard, G.~W.}
\newblock {\em The Collected Works of Leo Scilard: Scientific Papers}.
\newblock MIT Press, Cambridge, 1972.

\bibitem{fred-tof-82}
{\sc Fredkin, E., and Toffoli, T.}
\newblock Conservative logic.
\newblock {\em International Journal of Theoretical Physics 21\/} (1982),
  219--253.

\bibitem{glauber}
{\sc Glauber, R.~J.}
\newblock Amplifiers, attenuators and the quantum theory of measurement.
\newblock In {\em Frontiers in Quantum Optics}, E.~R. Pikes and S.~Sarkar, Eds.
  Adam Hilger, Bristol, 1986.

\bibitem{gruenbaum:68}
{\sc Gr{\"{u}}nbaum, A.}
\newblock {\em Modern Science and Zeno's paradoxes}, second edition~ed.
\newblock Allen and Unwin, London, 1968.

\bibitem{gruenbaum:74}
{\sc Gr{\"{u}}nbaum, A.}
\newblock {\em Philosophical Problems of Space of Time}, second, enlarged
  edition~ed.
\newblock D. Reidel, Dordrecht, 1973.

\bibitem{herbert}
{\sc Herbert, N.}
\newblock {FLASH}---a superluminal communicator based upon a new kind of
  quantum measurement.
\newblock {\em Foundation of Physics 12}, 12 (1982), 1171--1179.

\bibitem{hogarth1}
{\sc Hogarth, M.}
\newblock Predicting the future in relativistic spacetimes.
\newblock {\em Studies in History and Philosophy of Science. Studies in History
  and Philosophy of Modern Physics 24}, 5 (1993), 721--739.

\bibitem{hogarth2}
{\sc Hogarth, M.}
\newblock Non-{T}uring computers and non-{T}uring computability.
\newblock {\em PSA 1\/} (1994), 126--138.

\bibitem{ki-57}
{\sc Kirk, G.~S., and Raven, J.~E.}
\newblock {\em The Presocratic Philosophers}.
\newblock Cambridge University Press, Cambridge, 1957.

\bibitem{kreisel}
{\sc Kreisel, G.}
\newblock A notion of mechanistic theory.
\newblock {\em Synthese 29\/} (1974), 11--16.

\bibitem{landauer-87}
{\sc Landauer, R.}
\newblock Fundamental physical limitations of the computational process; an
  informal commentary.
\newblock {\em Cybernetics Machine Group Newsheet\/} (1/1/1987).

\bibitem{landauer:61}
{\sc Landauer, R.}
\newblock Irreversibility and heat generation in the computing process.
\newblock In {\em IBM Journal of Research and Development\/}
  \cite{maxwell-demon}, pp.~183--191.
\newblock Reprinted in \cite[pp. 188-196]{maxwell-demon}.

\bibitem{landauer-67}
{\sc Landauer, R.}
\newblock Wanted: a physically possible theory of physics.
\newblock {\em IEEE Spectrum 4\/} (1967), 105--109.

\bibitem{landauer:82}
{\sc Landauer, R.}
\newblock Uncertainty principle and minimal energy dissipation in the computer.
\newblock {\em International Journal of Theoretical Physics 21\/} (1982),
  283--297.

\bibitem{landauer-88}
{\sc Landauer, R.}
\newblock Dissipation and noise immunity in computation and communication.
\newblock {\em Nature 335\/} (1988), 779--784.

\bibitem{landauer-89}
{\sc Landauer, R.}
\newblock Computation, measurement, communication and energy dissipation.
\newblock In {\em Selected Topics in Signal Processing}, S.~Haykin, Ed.
  Prentice Hall, Englewood Cliffs, NJ, 1989, p.~18.

\bibitem{landauer}
{\sc Landauer, R.}
\newblock Information is physical.
\newblock {\em Physics Today 44\/} (May 1991), 23--29.

\bibitem{landauer-95}
{\sc Landauer, R.}
\newblock Advertisement for a paper {I} like.
\newblock In {\em On Limits}, J.~L. Casti and J.~F. Traub, Eds. Santa Fe
  Institute Report 94-10-056, Santa Fe, NM, 1994, p.~39.

\bibitem{landauer-94}
{\sc Landauer, R.}
\newblock Zig-zag path to understanding.
\newblock In {\em Proceedings of the Workshop on Physics and Computation
  PHYSCOMP '94\/} (Los Alamitos, CA, 1994), IEEE Computer Society Press,
  pp.~54--59.

\bibitem{zeno}
{\sc Lee, H. D.~P.}
\newblock {\em Zeno of Elea}.
\newblock Cambridge University Press, Cambridge, 1936.
\newblock reprinted by Adolf M. Hakkert, Amsterdam, 1967.

\bibitem{maxwell-demon}
{\sc Leff, H.~S., and Rex, A.~F.}
\newblock {\em Maxwell's Demon}.
\newblock Princeton University Press, Princeton, 1990.

\bibitem{le-91}
{\sc L{\'{o}}pez-Escobar, E. G.~K.}
\newblock {Z}eno's paradoxes pre {G}{\"{o}}delian incompleteness.
\newblock {\em Jahrbuch 1991 der Kurt-G{\"{o}}del-Gesellschaft\/} (1991), 49.

\bibitem{mandel:83}
{\sc Mandel, L.}
\newblock Is a photon amplifier always polarization dependent?
\newblock {\em Nature 304\/} (1983), 188.

\bibitem{mil-hard}
{\sc Milonni, P.~W., and Hardies, M.~L.}
\newblock Photons cannot always be replicated.
\newblock {\em Physics Letters 92A}, 7 (1982), 321--322.

\bibitem{e-f-moore}
{\sc Moore, E.~F.}
\newblock Gedanken-experiments on sequential machines.
\newblock In {\em Automata Studies}, C.~E. Shannon and J.~McCarthy, Eds.
  Princeton University Press, Princeton, 1956.

\bibitem{odi:89}
{\sc Odifreddi, P.}
\newblock {\em Classical Recursion Theory}.
\newblock North-Holland, Amsterdam, 1989.

\bibitem{pit:90}
{\sc Pitowsky, I.}
\newblock The physical {C}urch-{T}uring thesis and physical computational
  complexity.
\newblock {\em Iyyun 39\/} (1990), 81--99.

\bibitem{rogers1}
{\sc {Rogers, Jr.}, H.}
\newblock {\em Theory of Recursive Functions and Effective Computability}.
\newblock MacGraw-Hill, New York, 1967.

\bibitem{rosen}
{\sc Rosen, R.}
\newblock Effective processes and natural law.
\newblock In {\em The Universal Turing Machine. A Half-Century Survey},
  R.~Herken, Ed. Kammerer \& Unverzagt, Hamburg, 1988, p.~523.

\bibitem{rucker}
{\sc Rucker, R.}
\newblock {\em Infinity and the Mind}.
\newblock Birkh{\"{a}}user, Boston, 1982.
\newblock Reprinted by Bantam Books, 1986.

\bibitem{schaller-96}
{\sc Schaller, M., and Svozil, K.}
\newblock Automaton logic.
\newblock {\em International Journal of Theoretical Physics 35}, 5 (May 1996),
  911--940.

\bibitem{schrodinger}
{\sc Schr{\"{o}}dinger, E.}
\newblock Die gegenw{\"{a}}rtige {S}ituation in der {Q}uantenmechanik.
\newblock {\em Naturwissenschaften 23\/} (1935), 807--812, 823--828, 844--849.
\newblock English translation in \cite[pp. 152-167]{wheeler-Zurek:83}.

\bibitem{schroed:welt}
{\sc Schr{\"{o}}dinger, E.}
\newblock {\em Mein Leben, meine Weltansicht}.
\newblock Zsolnay, Vienna, 1985.
\newblock English translation: My view of the world, Cambridge University
  Press, Cambridge, 1964.

\bibitem{shor:94}
{\sc Shor, P.~W.}
\newblock Algorithms for quantum computation: discrete logarithms and
  factoring.
\newblock In {\em Proceedings of the 35th Annual Symposium of on Foundations of
  Computer Science, Santa Fe, NM, Nov. 20-22, 1994\/} (November 1994), IEEE
  Computer Society Press.
\newblock \\e-print http://xxx.lanl.gov/abs/quant-ph/9508027.

\bibitem{siegel95}
{\sc Siegelmann, H.~T.}
\newblock Computation beyond the {T}uring limit.
\newblock {\em Science 268\/} (1995), 545--548.

\bibitem{svozil-93}
{\sc Svozil, K.}
\newblock {\em Randomness \& Undecidability in Physics}.
\newblock World Scientific, Singapore, 1993.

\bibitem{svozil-nat-acad}
{\sc Svozil, K.}
\newblock A constructivist manifesto for the physical sciences.
\newblock In {\em The Foundational Debate, Complexity and Constructivity in
  Mathematics and Physics\/} (Dordrecht, Boston, London, 1995), W.~D.
  Schimanovich, E.~K{\"{o}}hler, and F.~Stadler, Eds., Kluwer, pp.~65--88.
\newblock Cf. \cite{svozil-complexity:95}.

\bibitem{maryland}
{\sc Svozil, K.}
\newblock On the computational power of physical systems, undecidability, the
  consistency of phenomena and the practical uses of paradoxa.
\newblock In {\em Fundamental Problems in Quantum Theory: A Conference Held in
  Honor of Professor John A. Wheeler. Annals of the New York Academy of
  Sciences {\bf 755}\/} (1995), D.~M. Greenberger and A.~Zeilinger, Eds., New
  York Academy of Sciences, pp.~834--841.

\bibitem{svozil-set}
{\sc Svozil, K.}
\newblock Set theory and physics.
\newblock {\em Foundations of Physics 25\/} (1995), 1541--1560.

\bibitem{svozil-complexity:95}
{\sc Svozil, K.}
\newblock How real are virtual realities, how virtual is reality? {T}he
  constructive re-interpretation of physical undecidability.
\newblock {\em Complexity 1}, 4 (1996), 43--54.

\bibitem{thom:54}
{\sc Thomson, J.~F.}
\newblock Tasks and supertasks.
\newblock {\em Analysis 15\/} (October 1954), 1--13.

\bibitem{weyl:49}
{\sc Weyl, H.}
\newblock {\em Philosophy of Mathematics and Natural Science}.
\newblock Princeton University Press, Princeton, 1949.

\bibitem{wheeler-Zurek:83}
{\sc Wheeler, J.~A., and Zurek, W.~H.}
\newblock {\em Quantum Theory and Measurement}.
\newblock Princeton University Press, Princeton, 1983.

\bibitem{wo-zu}
{\sc Wooters, W.~K., and Zurek, W.~H.}
\newblock A single quantum cannot be cloned.
\newblock {\em Nature 299\/} (1982), 802--803.

\end{thebibliography}
\end{document}