\documentstyle[amsfonts]{article}
%\documentstyle[svozil2]{article}
\begin{document}
%\renewcommand{\baselinestretch}{2}
 \title{On the computational power of physical systems,
undecidability, the consistency of phenomena and
 the practical uses of paradoxa}
\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 e1360dab@awiuni11.edvz.univie.ac.at}}
\maketitle

\begin{abstract}
Just as in mathematics, recursion theory and formal logic paradoxa can
be used to derive incompleteness theorems, physical paradoxa can be
applied for a derivation of constraints on the dynamics of physical
systems and of certain types of no-go theorems. For example,
time paradoxa can be used against the outcome controllability of
entangled
subsystems.  As a consequence, the requirement of consistency of
physical phenomenology induces the ``peaceful coexistence'' between
relativity theory and quantum mechanics.


\end{abstract}

\noindent
Undecidability in mathematics comes in different varieties;
so does undecidability in physics. In physics we have to make sure that
the theory is a suitable formal representation of the phenomenology. For
example, if the outcome of an experiment
cannot be predicted, does that mean that ``God plays dice?''
Or does it mean that although
the causes are in principle known, we are unable to compute a
prediction? Or does it simply mean that there are causes but these
are unknown
to us? These questions may never be fully settled \cite{frank}, but
since G\"odel's \cite{godel} and Turing's \cite{turing}
centennial findings, remarkable
advances have been made
in the formal perception of
undecidability. And today's computers not only serve as
number crunchers but are becoming a medium
to ``virtual'' realities. This greatly promotes the interaction between
theoretical computer sciences, formal logic and the physics of
``real'' reality.


Let us briefly consider the
physical correspondents of
two forms of mathematical undecidability, the first being associated
with the assumption of the
continuum (oracle computation), the second arising in the context of
finite computation.
If one wishes to order theories with respect to the computational power
necessary to implement them, continuum theories require more resources
than theories based on universal computation (e.g., Cellular Automata
\cite{fredkin,toffoli,feynman}), which in turn are more powerful than
finite models.


Continuum theories require the generation, storage and
processing of numbers which are uncomputable in the sense of Turing.
More precisely (and worse), ``almost all'' (with probability one)
elements of the continuum ``urn'' must be represented by random
sequences; stated pointedly:
any bit in its binary expansion is as uncorrelated to the previous and
the following bits as is any toss of a fair coin from other tosses
\cite{chaitin,calude}. In continuum theories, ``God plays dice.''
In such theories, undecidability, as not caused otherwise,
is implemented by
absolute randomness.
How come then, one may ask, that classical mechanics has been long
considered as the prototype for a ``deterministic'' model? The reason
for this is twofold: First, one may conjecture that it is possible to
keep
all the nice features of continuum mechanics (e.g.,
calculus) while at the same time get rid of the nasty aspects (e.g.,
nonconstructive randomness); and indeed there are indications that
this might be possible
\cite{bishop}. Second, there are ``nonchaotic'' dynamical systems, in
which arbitrary initial conditions  yield
solutions which converge rapidly toward periodic behaviour, or at
least converge toward a computable function (attractor).

Continuum theory (any dense set) allows the
construction of ``infinity machines,''
which could serve as oracles for the halting
problem.
Their construction closely follows Zeno's paradox of Achilles
and the Tortoise (Hector) by squeezing the time it takes for successive
steps of computation $\tau$ with geometric progression:
\unitlength=0.5mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(100.00,2.10)
\put(0.00,0.00){\line(1,0){100.00}}
\put(0.00,5.00){\makebox(0,0)[cc]{0}}
\put(0.00,-2.00){\line(0,1){4.00}}
\put(50.00,5.00){\makebox(0,0)[cc]{1}}
\put(50.00,-2.00){\line(0,1){4.00}}
\put(75.00,5.00){\makebox(0,0)[cc]{2}}
\put(75.00,-2.00){\line(0,1){4.00}}
\put(88.00,5.00){\makebox(0,0)[cc]{3}}
\put(88.00,-2.00){\line(0,1){4.00}}
\put(94.00,5.00){\makebox(0,0)[cc]{4}}
\put(94.00,-2.00){\line(0,1){4.00}}
\put(97.00,5.00){\makebox(0,0)[lc]{$\cdots$}}
\put(97.00,-2.00){\line(0,1){4.00}}
\put(99.00,-2.00){\line(0,1){4.00}}
\put(100.00,-2.00){\line(0,1){4.00}}
\put(99.67,-2.00){\line(0,1){4.00}}
\put(99.83,-2.00){\line(0,1){4.00}}
\put(99.50,-2.00){\line(0,1){4.00}}
\end{picture}
$\quad $
I.e.,
the time necessary for the $n$'th step becomes $\tau (n)=k^{n}$, $k<0$.
The limit of infinite computation is then reached in finite
physical time
$ \lim_{N\rightarrow \infty}\sum_{n=1}^N \tau{(n)}=
  \lim_{N\rightarrow \infty}\sum_{n=1}^N  k^n=
    1/(1-k)$. It can be shown by a
diagonalization argument that the
application of
such oracle subroutines
would result in a paradox in classical physics
(cf. \cite{svozil-93}, p. 24, 114).
Therefore, at least in this example, too powerful physical models (of
computation) are inconsistent.

A second type of undecidability which occurs in finite systems is
computational complementarity,
which is
realizable already at a very elementary pre-diagonalization level
\cite{e-f-moore}; i.e., without
the requirement of computational universality or its arithmetic
equivalent.
The resulting ``static'' automaton logic has great similarities to
quantum logic \cite{finkelstein-83,svozil-93}.

Our major concern here shall be a third type of undecidability.
It will be demonstrated how diagonalization techniques lead to
the exclusion of time paradoxa, and how quantum physics implements
causality.


Classical information theory (e.g., \cite{hamming}) is based on the bit
as
fundamental atom. This classical bit, henceforth called {\em cbit,} is
physically represented  by one of two classical states.
It is customary to use the symbols ``$0$'' and ``$1$'' as the names of
these states. The corresponding classical computational basis is
$\{0,1\}
={\Bbb Z}_2$.

In quantum information theory (cf.
\cite{a:8,deutsch-85,f-85,peres-85,b-86,m-86,deutsch:89,deutsch:92}),
the most elementary unit of information,
henceforth called {\em qbit},
may be physically represented by a coherent
superposition
of the two states which correspond to the symbols $0$ and $1$.
The corresponding quantum computational basis is the undenumerable set
$
\{ \vert a,b\rangle \mid \vert a,b\rangle =a\vert 0\rangle +b\vert 1
\rangle
,\; \vert a\vert^2+\vert b\vert^2=1,\; a,b\in {\Bbb C} \}
$.

In what follows we shall consider the hypothetical transmission of
information backward in time. To be more specific, we shall use an
EPR-type telegraph which uses entangled particles
in
a singlet state (i.e.,
the total angular momentum of the two particles is zero)
 as drawn in Fig.
\ref{fig-0}.
\begin{figure}
\begin{center}
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(91.00,85.00)
\put(74.00,20.00){\line(-1,1){59.00}}
\put(76.00,17.00){\makebox(0,0)[cc]{$t_S$}}
\put(45.00,40.00){\framebox(3.00,3.00)[cc]{$1$}}
\put(80.00,21.00){\framebox(3.00,3.00)[cc]{$2$}}
\put(15.00,85.00){\line(0,-1){15.00}}
\put(15.00,70.00){\circle*{2.83}}
\put(6.00,5.00){\vector(1,0){8.00}}
\put(6.00,5.00){\vector(0,1){8.00}}
\put(1.00,13.00){\makebox(0,0)[cc]{$t$}}
\put(14.00,0.00){\makebox(0,0)[cc]{$x$}}
\put(10.00,79.00){\makebox(0,0)[cc]{$t_A$}}
\put(91.00,32.00){\makebox(0,0)[cc]{$t_B$}}
\put(86.00,41.00){\circle{2.83}}
\put(86.00,26.00){\line(0,1){14.00}}
\put(74.00,20.00){\line(1,1){12.00}}
\put(15.00,79.00){\vector(3,-2){71.00}}
\end{picture}
\end{center}
\caption{Scheme of backward-in-time signalling by EPR-type telegraph.
The postulated controllability of outcomes in ${1}$, mediated
via ${2}$,
 is used
to transmit information. The flow of information is indicated by the
arrow. ``$\bullet$'' stands for the {\em active} mode; i.e.,
controllable outcome
(preparation). ``$\circ$'' stands for the {\em passive} mode; i.e.,
measurement. The two signs are drawn on top and at
bottom to indicate the orientation (relative angle $\pi$).
 \label{fig-0}}
\end{figure}
The apparatus is
tuned to convey perfect correlations of the direction of angular
momentum labelled by ``$+$'' and ``$-$''; i.e., the outcomes
are either $+\,+$ or $-\,-$. Perfect correlations can be achieved by
choosing a relative angle of measurement of $\pi$.
The (unphysical) assumption necessary for signalling backwards in
time is that on one side, say for particles in path ${1}$, the
{\em outcome can be controlled.}
This means that it will be assumed possible
to produce a particle with, say, direction of angular momentum
``$+$''
(``$-$'') in the path ${1}$ at $t_A$, thereby transmitting
a signal
``$+$'' (``$-$'') via its perfectly correlated entangled partner in
path ${2}$ to a second observer back in time at $t_B$; thereby,
$t_A>t_B>t_S$ but otherwise
arbitrary.

An alternative setup for information transmission backward in time
by an EPR-type {\em quantum} telegraph would use the
stronger-than-classical correlations for relative measurement angles
not equal to $0$, $\pi /2$ and $\pi$. In this case, the (unphysical)
assumption necessary for signalling backwards in
time is the {\em outcome dependence} on one side, say for particles in
path
${2}$, on the angle chosen for measurements on beam ${1}$
(e.g., by ``cloning,'' cf.
\cite{herbert,wo-zu-82,mil-har-82,mandel,glauber}).



Of course, this kind of {\em outcome control} or {\em outcome
dependence} would
neither be allowed in relativistic mechanics nor in quantum mechanics.
The
stronger-than-classical quantum expectation functions
are often considered manifestations
of ``nonlocality'' \cite{bell} (or, alternatively, of failure of
classical probability theory \cite{pitowsky}), but they only effect
parameter dependence, not outcome dependence of single events
\cite{shimony,shimony3}.

We shall make use of the EPR-type telegraph to construct a time paradox
and argue against outcome predictability and outcome controllability in
any form.
In a similar
manner, the liar paradox \cite{bible} was translated by G\"odel into
arithmetic
\cite{godel} to argue against a complete description of a formal system
within that very system \cite{burks}.
For instance, the g\"odelian sentence \cite{popper-50}
claiming its own
unprovability in a particular system appears undecidable within that
very system.
In physical terms,
undecidability must be translated onto the level of {\em
phenomena} and, only in a secondary step, into their theoretic
description.
On the phenomenological level there is no such
thing as an inconsistent phenomenon.
In a typical {\em yes-no} experiment which can have two
possible outcomes, only one of these outcomes will actually be measured.
However, this uniqueness of phenomenology does not guarantee that
a theory exists which predicts it completely.
There might even be a ``meta-physical''  (extrinsic \cite{svozil:83},
exo-
\cite{roessler}) arena in which this particular
outcome could be
deterministically accounted for. Yet,
for an intrinsic observer who is embedded in the system
\cite{toffoli:79},
this
``meta-physical'' level might be permanently inaccessible
\cite{ro-cp,svozil-93}. As will be shown below, quantum
mechanics implements this phenomenological undecidability both by the
postulate of randomness of certain outcomes and by the superposition
principle.
Related arguments have been put forward in
\cite{popper-50,rothstein-82,peres-84,wolfram1,moore,elitzur,posiewnik}.


Consider two
backward-in-time signalling
EPR-type telegraphs of the above type arranged
as drawn in Fig. \ref{f-1}.
Physically, the flow of information is mediated via the two entangled
pairs in paths {1}--{2} and {3}--{4}.
An information  in  2 is mirrored by $M$ in 3.
By this instrument, some mechanistic agent $A$ (e.g., computer,
deterministic observer) which is given the power of outcome control
can exchange information
with itself on closed timelike lines
\cite{godel-rmp,deutsch-91}.
Agent $A$ shall be confronted with the following paradoxical task.
\begin{figure}
\begin{center}
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(92.00,125.00)
\put(16.00,20.00){\line(1,-1){10.00}}
\put(26.00,10.00){\line(1,1){60.00}}
\put(75.00,60.00){\line(-1,1){59.00}}
\put(77.00,57.00){\makebox(0,0)[cc]{$S_1$}}
\put(28.00,6.00){\makebox(0,0)[cc]{$S_2$}}
\put(75.00,60.00){\line(1,1){11.00}}
\put(16.00,119.00){\vector(3,-2){70.00}}
\put(86.00,72.33){\vector(-4,-3){70.00}}
\put(46.00,80.00){\framebox(3.00,3.00)[cc]{$1$}}
\put(86.00,58.00){\makebox(0,0)[cc]{$M$}}
\put(75.00,68.00){\framebox(3.00,3.00)[cc]{$2$}}
\put(59.00,35.00){\framebox(3.00,3.00)[cc]{$3$}}
\put(22.00,16.00){\framebox(3.00,3.00)[cc]{$4$}}
\put(16.00,125.00){\line(0,-1){15.00}}
\put(16.00,110.00){\circle*{2.83}}
\put(86.00,80.00){\line(0,-1){16.00}}
\put(16.00,12.00){\circle{2.83}}
\put(86.00,81.00){\circle{4.47}}
\put(86.00,81.00){\circle*{2.83}}
\put(16.00,13.00){\line(0,1){13.00}}
\put(16.00,70.00){\circle{14.00}}
\put(16.00,70.00){\makebox(0,0)[cc]{$D$}}
\put(16.00,30.00){\vector(0,1){32.00}}
\put(16.00,78.00){\vector(0,1){28.00}}
\put(6.00,5.00){\vector(1,0){8.00}}
\put(6.00,5.00){\vector(0,1){8.00}}
\put(1.00,13.00){\makebox(0,0)[cc]{$t$}}
\put(14.00,0.00){\makebox(0,0)[cc]{$x$}}
\put(11.00,119.00){\makebox(0,0)[cc]{$t_A$}}
\put(11.00,20.00){\makebox(0,0)[cc]{$t_{A'}$}}
\put(92.00,72.00){\makebox(0,0)[cc]{$t_B$}}
\end{picture}
\end{center}
\caption{time paradox.
 \label{f-1}}
\end{figure}
Whenever $A$ registers the information ``$+$'' (``$-$'') at time
$t_{A'}$,
$A$ must stimulate the opposite outcome ``$-$'' (``$+$'') at the later
time
$t_A$.

Before discussing the paradox, let us consider the two states
$\vert 0\rangle \equiv$ ``$-$''
and
$\vert 1\rangle \equiv$ ``$+$'' which are accessible to $A$.
These states can be the basis of a cbit with the identification
of the
symbols ``$0$'' and ``$1$'' for
$\vert 0\rangle$
and
$\vert 1\rangle $,
 respectively.
Quantum mechanically any coherent superposition of them is allowed.
Agent $A$'s paradoxical task can be formalized
by a unitary evolution operator
$
\widehat{D}
$ as follows
\begin{equation}
\widehat{D} \vert 0\rangle  = \vert 1\rangle , \quad
\widehat{D} \vert 1\rangle  = \vert 0\rangle \quad .
\end{equation}
In the state basis $\{ \vert 0\rangle , \vert 1\rangle \}$
($\tau_1$ stands for the Pauli spin operator),
\begin{equation}
\widehat{D}=
\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    \quad .
\end{equation}
The syntactic structure of the
paradox closely resembles Cantor's  diagonalization me\-thod
which has been
applied by G\"odel, Turing and others for undecidability proofs in a
recursion theoretic setup \cite{davis,rogers,odi:89,svozil-93}.
Therefore,
$
\widehat{D}
$
will be called
{\em diagonalization} operator,
despite the fact that its only nonvanishing components are
off-diagonal.
(Notice that $A$'s task would be perfectly consistent if
there were no ``bit switch'' and if thus
$
\widehat{D} =
{\Bbb I}
$.)

The paradoxical feature of the construction reveals itself in the
following question: what happens to agent $A$?
In particular: what does $A$ register and send?

Let us first consider these questions from a classical perspective.
Classically, the particles with which $A$ operates can only be in one of
two possible
states, namely in $\vert 0\rangle $ or in $\vert 1\rangle $, corresponding to
the classical computational basis ${\Bbb Z}_2$.
By measuring the particle in beam 4, $A$ gets either the outcome ``$+$''
or ``$-$''.
In both cases, agent $A$ is lead to a complete
contradiction.

For, if $A$
receives ``$+$'', corresponding to cbit state 1,
$A$ is obliged to send out ``$-$'',
corresponding to cbit state
0
($A$ has been assumed to be able to control the outcomes in beam 1).
Due to the perfect EPR-correlations, the
partner particle in beam
2 is registered as
``$-$'' at the mirror at time $t_B$. By controlling the outcome in beam
3, this mirrored cbit can again be sent backwards in time, where ``$-$''
is received by
$A$ via a measurement of the particle in beam 4. This, however,
contradicts
the initial assumption that the outcome in beam 4 is ``$+$''.

On the other hand,
if $A$
receives ``$-$'', corresponding to cbit state 0,
 $A$ is obliged to send out ``$+$'', corresponding to cbit state 1;
yet, since at $t_B$ the cbit is just
reflected as described above,
$A$ should have received ``$+$''.
Thus classically, agent $A$ is in an inescapable dilemma.

The defense strategy in formal logic and classical recursion theory
against such inconsistencies is
to avoid the appearance of a paradox by claiming (stronger: requiring)
overall consistency, resulting in no-go theorems; i.e., in the
postulate of the impossibility of any operational method, procedure or
device which would have the potentiality to cause a paradox.
(Among the many impossible objects giving rise to paradoxes are
such seemingly innocent devices as a
``halting
 algorithm'' computing whether or not another
arbitrary computable algorithm produces a particular output;
or an algorithm identifying
another arbitrary algorithm by input-output experiments.)

In the above case, the defense strategy would result in the postulate of
the impossibility of any
backward-in-time
information flow or, more general,
of closed timelike lines.
Since the only nontrivial feature of the backward-in-time
information flow has been outcome controllability or outcome dependence,
the diagonalization
argument can be used against outcome controllability and outcome
dependence, resulting in an
intrinsic randomness of the individual outcomes.

Quantum mechanics implements exactly that kind of recursion theoretic
argument; yet in a form which is not common in recursion theory. Observe
that the paradox is resolved when
$A$ is allowed a nonclassical qbit of information.
In particular, agent $A$'s task can consistently be performed
if it inputs a qbit corresponding to the {\em fixed point} state
of
$\widehat{D}$; i.e.,
\begin{equation}
\widehat{D}\vert \ast \rangle =\vert \ast \rangle \quad .
\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 qbit
in the basis of $\vert 0\rangle $ and $\vert 1\rangle $ is given by
\begin{equation}
\vert \ast \rangle =\vert {1\over 2},{1\over 2} \rangle =\vert I\rangle \quad .
\end{equation}
This qbit solution corresponds to the statement that it is impossible
for the agent to control the outcome; a situation actually
encountered
in quantum mechanics \cite{fp}.


We close the discussion on the consistent use of paradoxa in physics
with a few comments. First, it is important to recognize that the above
considerations have {\em no} immediate bearing on quantum
complementarity.
In the author's opinion, complementarity is a general feature of the
intrinsic perception of computer-generated universes, which is
realizable already at a very elementary pre-diagonalization level
\cite{e-f-moore,finkelstein-83,svozil-93}; i.e., without
the requirement of computational universality or its arithmetic
equivalent.

Second,
the above argument remains valid
for any conceivable (local or nonlocal
\cite{pitowsky-82,pitowsky})
 hidden
variable theory.
The consistency of the physical
phenomenology requires that hidden variables remain inaccessible to an
intrinsic observer.
From an intrinsic, operational point of view, a paradox always
marks the appearance of uncertainty and uncontrollability.

Third,
an application for quantum information theory is
the handling of inconsistent information in databases.
Thereby,
two contradicting cbits of information
$\vert a\rangle $ and
$\vert b\rangle $ are resolved by the qbit
$\vert {1\over 2},{1\over 2} \rangle =
({1/ \sqrt{2}})(\vert a\rangle + \vert b\rangle )$.
Throughout the rest of the computation the coherence is maintained.
After the processing, the result is obtained by a
measurement. The processing of qbits requires an exponential space
overhead on classical computers in cbit base \cite{feynman}.
Thus, in order to remain tractable,
the corresponding qbits should be implemented on
truly quantum universal computers.



\begin{thebibliography}{99}

\bibitem{frank}
Ph. Frank, {\sl Das Kausalgesetz und seine Grenzen}
(Springer, Vienna 1932).

\bibitem{godel}
K. G\"odel, {\sl Monatshefte f\"ur Mathematik und Physik}
{\bf 38}, 173 (1931);
English translation in \cite{godel-ges1}.


 \bibitem{godel-ges1}
 K. G\"odel, {\sl Collected Works, Volume I, Publications 1929-1936},
 ed. by S. Feferman, J. W. Dawson, Jr., St. C. Kleene, G. H. Moore, R.
 M. Solovay, J. van Heijenoort (Oxford University Press, Oxford, 1986).

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

\bibitem{fredkin}
 E. Fredkin, {\sl International Journal of Theoretical Physics} {\bf
21}, 219 (1982);
 {\sl Physica} {\bf D45}, 254 (1990).

 \bibitem{toffoli}
 T. Toffoli and N. Margolus, {\sl Cellular Automata Machines} (MIT
 Press, Cambridge, Massachusetts, 1987).

 \bibitem{feynman}
R. P. Feynman, {\sl International Journal of Theoretical Physics}
{\bf 21}, 467 (1982).

\bibitem{chaitin}
G. J. Chaitin, {\sl Int. J. Theoret. Physics} {\bf 21}, 941 (1982);
 reprinted in
G. J. Chaitin, {\sl Information, Randomness and Incompleteness, Second
edition}
(World Scientific, Singapore, 1987, 1990).

\bibitem{calude}
 C. Calude,
{\sl Information and Randomness --- An Algorithmic Perspective}
(Springer, Berlin, 1994).


 \bibitem{bishop}
 E. Bishop and D. S. Bridges, {\sl Constructive Analysis} (Springer,
 Berlin, 1985).

\bibitem{svozil-93}
K. Svozil,  {\sl Randomness and Undecidability in Physics}
(World Scientific, Singapore, 1993).

 \bibitem{e-f-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{finkelstein-83}
 D. Finkelstein and S. R. Finkelstein,
 {\sl International Journal of Theoretical Physics} {\bf 22}, 753
 (1983).


 \bibitem{hamming}
 R. W. Hamming, {\sl Coding and Information Theory, Second Edition}
 (Prentice-Hall, Englewood Cliffs, New Jersey, 1980).

 \bibitem{a:8}
 D. Z. Albert, {\sl Phys. Lett.} {\bf 94A}, 249 (1983).

 \bibitem{deutsch-85}
 D. Deutsch, {\sl Proc. R. Soc. Lond.} {\bf A 400}, 97 (1985).

 \bibitem{f-85}
R. P. Feynman, {\sl Opt. News} {\bf 11}, 11 (1985).

 \bibitem{peres-85}
 A. Peres, {\sl Phys. Rev.} {\bf A32}, 3266 (1985).

 \bibitem{b-86}
 P. Benioff, {\sl Annals New York Akademy of Sciences} {\bf 480}, 475
 (1986).

 \bibitem{m-86}
 N. Margolus, {\sl Annals New York Akademy of Sciences} {\bf 480}, 487
 (1986).

 \bibitem{deutsch:89}
 D. Deutsch, {\sl Proc. R. Soc. Lond.} {\bf A 425}, 73 (1989).

 \bibitem{deutsch:92}
 D. Deutsch and R. Jozsa, {\sl Proc. R. Soc. Lond.} {\bf A 439}, 553
(1992).

\bibitem{herbert}
N. Herbert, {\sl Foundation of Physics} {\bf 12}, 1171 (1982).

\bibitem{wo-zu-82}
W. K. Wooters and W. H. Zurek,
{\sl Nature} {\bf 299}, 802 (1982).

\bibitem{mil-har-82}
P. W. Milonni and M. L. Hardies,
{\sl Phys. Lett.} {\bf 92A}, 321 (1982).

\bibitem{mandel}
L. Mandel,
{\sl Nature} {\bf 304}, 188 (1983).

 \bibitem{glauber}
 R. J. Glauber, {\sl Amplifyers, Attenuators and the Quantum Theory of
 Measurement}, in {\sl Frontiers in Quantum Optics}, ed. by E. R. Pikes
 and S. Sarkar (Adam Hilger, Bristol 1986).

 \bibitem{bell}
 J. S. Bell, {\sl Physics} {\bf 1}, 195 (1964);
 J. S. Bell, {\sl Speakable and Unspeakable in Quantum Mechanics}
 (Cambridge University Press, Cambridge, 1987).

 \bibitem{pitowsky}
 I. Pitowsky, {\sl Quantum Probability $-$ Quantum Logic} (Springer,
 Berlin, 1989).


 \bibitem{shimony}
 A. Shimony, {\sl Controllable and uncontrollable non-locality}, in
 {\sl Proc. Int. Symp. Foundations of Quantum Mechanics}, ed. by S.
 Kamefuchi {\it et al.} (Physical Society of Japan, Tokyo, 1984).

 \bibitem{shimony3}
 A. Shimony, {\sl Events and Processes in the Quantum World}, in {\sl
 Quantum Concepts in Space and Time}, ed. by R. Penrose and C. I. Isham
 (Clarendon Press, Oxford, 1986).

\bibitem{bible}
 The {\sl Bible} contains a passage, which
 refers to Epimenides, a Crete living in the capital city of
 Cnossus:
 {\it ``One of themselves, a prophet of their own, said, `Cretans are
 always liars, evil beasts, lazy gluttons.'  ''} --- St. Paul,
 Epistle to Titus I (12-13).
 For more details, see
 A. R. Anderson, {\sl St. Paul's epistle to Titus}, in {\sl The Paradox
 of the Liar}, ed. by R. L. Martin (Yale University Press, New Haven,
 1970).


 \bibitem{davis}
 M. Davis, {\sl The Undecidable} (Raven Press, New York, 1965).

 \bibitem{godel-rmp}
K. G\"odel, {\sl Rev. Mod. Phys.} {\bf 21}, 447 (1949):
K. G\"odel, {\sl A remark about the relationship between relativity
theory and idealistic philosophy}, in
{\sl Albert Einstein, philosopher-scientist}, ed. by P. A. Schilpp
(Evanston, Ill., 1949),
p. 555.

\bibitem{deutsch-91}
D. Deutsch, {\sl Phys. Rev.} {\bf D44}, 3197 (1991).

\bibitem{burks}
The following citation is taken from K. G\"odel's reply to a letter by
A. W.
 Burks, reprinted in J. von Neumann's
 {\sl Theory of Self-Reproducing Automata}, ed. by A. W. Burks
 (University of Illinois Press, Urbana, 1966),
 p. 55; see also
  S. Feferman, {\sl Philosophia Naturalis} {\bf 21}, 546 (1984), p.
 p. 554:

 {\em
 ``$\ldots$
  the fact that a complete epistemological description
 of a language $A$ cannot be given in the same language $A$, because
 the concept of truth of sentences of $A$ cannot be defined in $A$. It
 is this theorem which is the true reason for the existence of
 undecidable propositions in the formal systems containing
arithmetic.''}


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

\bibitem{svozil:83}
K. Svozil,
{\sl Europhysics Letters} {\bf 2}, 83 (1986);
 {\sl Il Nuovo Cimento} {\bf 96B}, 127 (1986); and \cite{svozil-93},
chapter 6.

\bibitem{roessler}
 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;
 O. E. R\"ossler, {\sl Endophysics, Die Welt des inneren Beobachters},
 ed. by P. Weibel (Merwe Verlag, Berlin, 1992).

 \bibitem{toffoli:79}
 T. Toffoli,
{\sl The role of the observer in uniform systems}, in {\sl Applied
General Systems Research}, ed. by G. Klir (Plenum Press, New York,
London, 1978).

\bibitem{ro-cp}
The observer is situated, in
O. E. R\"ossler's dictum, in a ``Cartesian prison;''
cf.
H. Atmanspacher
and G. Dalenoort, eds., {\sl Inside Versus Outside}
(Springer, Berlin, 1994), p. 156.


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

 \bibitem{peres-84}
 A. Peres, {\sl Foundation of Physics} {\bf 15}, 201 (1985).

\bibitem{wolfram1}
St. Wolfram, {\sl Physical Review Letters} {\bf 54}, 735 (1985);
{\sl Physica} {\bf D10}, 1 (1984);
{\sl Rev. Mod. Phys.} {\bf 55}, 601 (1983).


 \bibitem{moore}
 Ch. D. Moore, {\sl Phys. Rev. Lett.} {\bf 64}, 2354 (1990);
cf. Ch. Bennett, {\sl Nature} {\bf 346}, 606 (1990).

\bibitem{elitzur}
A. C. Elitzur, {\sl Phys. Lett.} {\bf A167}, 335 (1992), as well as
S. Popescu and D. Rohrlich,
{\sl Foundations of Physics}
{\bf 24}, 379 (1994) refer to a talk of
Professor Y. Aharonov delivered at the Einstein centennial.


\bibitem{posiewnik}
A. Posiewnik, {\sl On inconsistency of the language of physics}
(University of Gdansk preprint, 1993).


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

\bibitem{odi:89}
P. Odifreddi, {\sl Classical Recursion Theory}
(North-Holland, Amsterdam, 1989).


\bibitem{fp}
In an abstract form, the above argument is the analogon to
the fixed point or paradoxical combinator in combinatory logic;
cf.
 H. B. Curry and R. Feys, {\sl Combinatory Logic} (North-Holland,
 Amsterdam, 1958),
p. 151, 178 and
 H. P. Barendregt, {\sl The Lambda Calculus (Revised Edition)}
 (North Holland, Amsterdam, 1984).

 \bibitem{pitowsky-82}
 I. Pitowsky, {\sl Phys.
 Rev. Lett.} {\bf 48}, 1299 (1982); {\sl Phys. Rev.} {\bf D27}, 2316
 (1983); N. D. Mermin, {\sl Phys. Rev. Lett.}
 {\bf 49}, 1214 (1982); A. L. Macdonald, {\it Ibid.}, 1215 (1982); I.
 Pitowsky, {\it Ibid.}, 1216 (1982).

\end{thebibliography}
\end{document}