\documentclass[rmp,amsfonts,showpacs,showkeys]{revtex4}
%\documentclass[pra,showpacs,showkeys,amsfonts]{revtex4}
\usepackage{graphicx}
%\documentstyle[amsfonts]{article}
\RequirePackage{times}
%\RequirePackage{courier}
\RequirePackage{mathptm}
%\renewcommand{\baselinestretch}{1.3}

\begin{document}
%\sloppy




\title{Physics and metaphysics look at computation}

\author{Karl Svozil}
\email{svozil@tuwien.ac.at}
\homepage{http://tph.tuwien.ac.at/~svozil}
\affiliation{Institut f\"ur Theoretische Physik, University of Technology Vienna,
Wiedner Hauptstra\ss e 8-10/136, A-1040 Vienna, Austria}


\begin{abstract}
As far as algorithmic thinking is bound by symbolic paper-and-pencil operations,
the Church-Turing thesis appears to hold.
But is physics, and even more so, is the human mind, bound by symbolic paper-and-pencil operations?
What about the powers of the continuum, the quantum, and what about human intuition, human thought?
These questions still remain unanswered.
With the strong Artificial Intelligence assumption, human consciousness is
just a function of the organs
(maybe in a very wide sense and not only restricted to neuronal brain activity),
and thus the question is relegated to physics.
In dualistic models of the mind, human thought transcends symbolic paper-and-pencil operations.
\end{abstract}

\pacs{03.67.Hk}
\keywords{Church-Turing thesis, Quantum information, Zeno squeezing, Dualism}

\maketitle

\tableofcontents

\section{Computation is physical}

It is not unreasonable 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.}
In this way, the physical realization confers power to the formal method.

Conversely, the formalism might ``reveal'' some ``laws'' or structure in the
physical processes.
With the Church-Turing thesis, physics also acquires a definite, formalized
concept of ``physical determinism'' as well as ``undecidability,'' which is lacking
in pre-Church-Turing times.
Indeed, the Church-Turing thesis can be perceived as part of
physics proper, and its assumption be interpreted as indication that
the Universe amounts to a huge computational process;
a suspicion already pursued by the Pythagoreans.
Such perception does not fix the lapse of evolution in a Laplacian-type
monotony entirely, but still allows for dualism and ``miracles''
through the influx of information from interfaces, as will be discussed below.

The recognition of the physical aspect of the Church-Turing thesis---the
postulated equivalence between the informal notion of ``algorithm,''
and recursive function theory as its formalized
counterpart---is not new
\cite{scilard-col,brillouin1,brillouin2,maxwell-demon,rogers1,odi:89,pit:90,galindo-02}. In particular
Landauer
has pointed out on many occasions
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}
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}

In what follows, we shall briefly review some aspects of the interrelationship
between physics and computation.
We believe that it is the nature of the subject itself which prevents a definite
answer to many questions, in particular to a ``canonical'' model of computation
which might remain intact as physics and the sciences evolve.
So, we perceive this review as a snapshot about the present status
of our thinking on feasible computation.


\section{Paper-and-pencil operations in physics}

After Alonzo Church \cite{church30,church36} conceptualized an equivalent notion of ``effective computability''
with an ``Entscheidungsproblem'' (decision problem) in mind
which was quite similar to the questions G\"odel pursued in Ref.~\cite{godel1},
Alan Turing \cite{turing-36} enshrined that part of mathematics, which can be ``constructed''
by paper and pencil operations, into a Turing machine which possesses a potentially
unbounded one-dimensional tape divided into cells,
some finite memory and some
read-write head which transfers back and forth information from the tape to this memory.
A table of transition rules figuring as the ``program'' steers the machine deterministically.
The behaviour of a Turing machine may also be determined by its initial state.
%            http://plato.stanford.edu/entries/turing-machine/  http://www.abelard.org/turpap2/tp2-ie.asp

Furthermore, a universal Turing machine is capable
of simulating all other Turing machines (including itself).
According to Turing's definition stated in Ref.~\cite{turing-36},
a number is computable if its decimal can be written down by a machine.
In view of the ``algorithm'' created by Chaitin \cite{chaitin3,calude:02} to ``compute''
the halting probability and encodable by almost every conceivable programming language such as C or Algol,
one should add the proviso that any such Turing computable number should have a computable radius of convergence.

It turned out that Turing's notion of computability, in particular universal computability,
is quite robust in the sense that
it is equivalent to the recursive functions \cite{rogers1,odi:89}, abacus machines, or the usual
modern digital computer (given ``enough'' memory) based on the von Neumann architecture,
on which for instance this manuscript has been written and processed.

It is hardly questionable that Turing's model can be embedded
in physical space-time; at least in principle.
A discretization of physical space,
accompanied by deterministic evolution rules,
presents no conceptual challenge for a physical realization.
After all, Turing's conceptualization started from the intuitive
symbolic handling of the mathematical entities that every pupil is drilled to obey.
Even grown-up individuals arguably lack
an understanding of those rules imposed upon them and thus lack the semantics;
but this ignorance does not stop them from applying the syntax correctly, just as a Turing machine does.

There are two problems and two
features of any concrete technical realization of Turing machines.

(P1)
On all levels of physical realization, errors occur
due to malfunctioning of the apparatus.
This is unavoidable.
As a result, all our realistic models of computation must be
essentially probabilistic.

(P2)
From an operational perspective \cite{bridgman,bridgman52},
all physical resources are strictly finite and cannot be unbounded;
even not potentially unbounded
\cite{gandy1,gandy2}.

(F1)
It comes as no surprise that any embedding of a universal Turing machine,
and even more so less powerful finitistic computational concepts,
into a physical system results in physical undecidability.
In case of computational universality, this is due to a reduction to
the recursive unsolvability of the halting problem.
Ever after G\"odel's and Tarsky's destruction of the finitistic program of
Hilbert, Kronecker and others to find a finite set of axioms from which to derive
all mathematical truth, there have been attempts to translate these results into some
relevant physical form (e.g., see
Ref.~\cite{popper-50i,popper-50ii,moore,svozil-93,casti:94-onlimits_book,casti:96-onlimits}).

(F2)
The recursive undecidability of the
rule inference problem \cite{go-67} states that for any mechanistic agent
there exists a total
recursive function
such that the agent cannot infer this function.
In more physical terms,
there is no systematic way of finding a deterministic law from the
input-output analysis of a (universal) mechanistic physical system.

The undecidabilities resulting from (F1)\&(F2) should not be confused with
another mode of undecidability.
Complementarity is
a quantum mechanical feature also occurring in finite automata theory
\cite{e-f-moore,conway,svozil-93,schaller-96,dvur-pul-svo,cal-sv-yu,svozil-ql}
and generalized urn models \cite{wright:pent,wright},
two models having a common logical; i.e., propositional structure \cite{svozil-2001-eua}.


\section{Cantor's paradises and classical physics}

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.}
If one assumes a correspondence between
(physical) theory and physical systems
\cite{svozil-set,sv-aut-rev},
how does the continuum and its associated pandemonium of effects
(such as the Banach-Tarski paradox \cite{wagon1,pitowsky-82,svo-neufeld}; see also Ref.~\cite{siegel95})
fit into this picture?

\subsection{Computational correspondence between formal and physical entities}

According to the standard physics textbooks,
physical theory requires ``much'' richer structures than are
provided by universal Turing computability.
Physical theories such as (pre-quantum) mechanics \cite{goldstein}
and electrodynamics \cite{jackson} in various ways assume the continuum,
for example configuration space-time,
phase space, field observables and the like.
Even quantum mechanics is a theory based upon continuous space and time
as well as on a continuous wave function,
a fact which stimulated Einstein to remark (at the end of Ref.~\cite{ein1})
that maybe we should develop
quantum theory radically further into a purely discrete formalism.

Note that, with probability one, any element of the continuum is neither
Turing computable, nor algorithmically compressible; and thus random
\cite{chaitin3,calude:02}.
Thus, assuming that initial values of physical systems
are arbitrary elements ``drawn'' from some
``continuum urn''
amounts to assuming that in almost all cases they cannot be represented by
any constructive, computable method.
Worse yet, one has to assume the physical system has a capacity
associated with the axiom of choice in order to even make sure
that such a draw is possible.
Because how could one draw; i.e., select, an initial value,
whose representation cannot be represented in any conceivable algorithmic way?

These issues have become important for the conceptual foundation of chaos theory.
In the ``deterministic chaos'' scenario the deterministic equation of motion
appears to ``reveal'' the randomness; i.e.,
the algorithmically incompressible information
of the initial value \cite{shaw,schuster1,pit:96}.


Another issue is the question of the
preservation of computability in classical analysis,
the physical relevance of  Specker's theorems \cite{specker-ges,wang,kreisel},
as well as the more recent constructions  by Pour-El and Richards \cite{pr1}
(cf. objections raised by Bridges
\cite{bridges1} and Penrose \cite{penrose:90});
see also Ref.~\cite{cal-sv-yu}.

\subsection{Infinity machines}

For the sake of exposing the problems associated with
continuum physics explicitly, an
oracle will be introduced
whose capacity exceeds  and outperforms any universal Turing machine.
Already Hermann 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;
see also
 Gr\"unbaum
\cite[p. 630]{gruenbaum:74}, 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
Beth
 \cite[p. 492]{beth-59}
 and
L\'opez-Escobar
 \cite{le-91}, and the author \cite[pp. 24-27]{svozil-93} for related discussions.
Weyl writes \cite[p. 42]{weyl:49},
 \begin{quote}
 {\em
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}



The oracle's
 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.
 In order to achieve the limit,
 two time scales are introduced: the {\em intrinsic time $t$
 of the process of computation}, which approaches infinity in finite
{\em
 extrinsic or proper time $\tau$ of some outside observer}.
The
time scales $\tau$ and $t$
 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 operationalizations; 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}
Note that for the oracle model introduced here
merely
dense space-time would be required.


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 halting probability \cite{chaitin3,calude:02}
 in finite proper time.


There is no commonly accepted physical principle which would forbid
such an oracle {\it a priori}.
One
might argue that any such 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 geometricaly decreasing progression in energy
consumption, at least up to some limiting (e.g., Planck) scale.

\section{Quantum oracles}

In the light of the quanta, the Church-Turing thesis, and in particular quantum recursion theory,
might have to be extended.
We first present an algorithmic form of a modified diagonalization procedure
in quantum mechanics due to the existence of fixed points of quantum information
\cite{deutsch91,svozil-paradox,ord-kieu-03}.
Then we shortly discuss quantum computation and mention recent proposals
extending the capacity of quantum computation beyond the Church-Turing barrier.

\subsection{Diagonalization method in quantum recursion theory}

Quantum bits can be physically represented by a coherent
superposition
of the two classical bit states denoted by $t$ and $f$.
The quantum bit states
\begin{equation}
x_{\alpha ,\beta}  =\alpha t+\beta f
\end{equation}
form a continuum, with
$ \vert \alpha \vert^2+\vert \beta \vert^2=1$, $\alpha ,\beta \in {\Bbb
C}$.

For the sake of
contradiction, consider a universal computer $C$ and  an arbitrary algorithm
$B(X)$ whose input is a string of symbols $X$.  Assume that there exists
a ``halting algorithm'' ${\tt HALT}$ which is able to decide whether $B$
terminates on $X$ or not.
The domain of ${\tt HALT}$  is the set of legal programs.
The range of ${\tt HALT}$ are classical bits (classical case) and quantum bits (quantum
mechanical case).

Using ${\tt 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
$\ulcorner B\urcorner $,
i.e., as a string of
symbols.  In the next step, the agent uses the code
$\ulcorner B\urcorner $
 as input
string for $B$ itself; i.e., $A$ forms  $B(\ulcorner B\urcorner )$,
henceforth denoted by
$B(B)$.  The agent now hands $B(B)$ over to its subroutine ${\tt HALT}$.
Then, $A$ proceeds as follows:  if ${\tt HALT}(B(B))$ decides that
$B(B)$ halts, then the agent $A$ does not halt; this can for instance be
realized by an infinite {\tt DO}-loop; if ${\tt HALT}(B(B))$ decides
that $B(B)$ does {\em not} halt, then $A$ halts.

The agent $A$ will now be confronted with the following paradoxical
task:  take the own code as input and proceed.

\subsubsection{Classical case}
 Assume that $A$ is
restricted to classical bits of information.
To be more specific,
assume that ${\tt HALT}$ outputs the code of a classical bit as follows
($\uparrow$ and $\downarrow$ stands for divergence and convergence,
respectively):
\begin{equation}
{\tt HALT} ( B(X) ) =\left\{
 \begin{array}{l}
0 \mbox{ if } B(X) \uparrow
\\
1 \mbox{ if } B(X) \downarrow \\
\end{array}
 \right.
\quad .
\label{el:halt}
\end{equation}


Then, whenever $A(A)$
halts, ${\tt HALT}(A(A))$ outputs $1$ and forces $A(A)$ not to halt.
Conversely,
whenever $A(A)$ does not halt, then ${\tt HALT}(A(A))$ outputs $0$
and steers
$A(A)$ into the halting mode.  In both cases one arrives at a complete
contradiction.  Classically, this contradiction can only be consistently
avoided by assuming the nonexistence of $A$ and, since the only
nontrivial feature of $A$ is the use of the peculiar halting algorithm
${\tt HALT}$, the impossibility of any such halting algorithm.


\subsubsection{Quantum mechanical case}
As has been argued above, in quantum information theory
a quantum bit may be in a coherent
superposition
of the two classical states $t$ and $f$.
Due to this possibility of a coherent superposition of classical bit
states, the usual {\it reductio ad absurdum} argument breaks down.
Instead, diagonalization procedures in
quantum information theory yield quantum bit solutions which are fixed points
of the associated unitary operators.


In what follows it will be demonstrated how the task of the agent $A$
can be performed consistently if
$A$ is allowed to process quantum information.
To be more specific, assume that the output of the hypothetical
``halting algorithm'' is a quantum bit
\begin{equation}
{\tt HALT} ( B(X) ) = x_{\alpha , \beta}
\quad .
\end{equation}
We may think of   ${\tt HALT} ( B(X) )$ as a universal computer $C'$
simulating $C$ and containing a dedicated {\em halting bit}, which it
the output of $C'$
at every (discrete) time cycle. Initially (at time zero),
this halting bit is prepared to be a 50:50 mixture of the
classical halting and non-halting states $t$ and $f$; i.e.,
$x_{1/\sqrt{2} , 1/\sqrt{2} }$. If later $C'$ finds that $C$ converges
(diverges) on $B(X)$, then the halting bit of $C'$ is set to the
classical value $t$ ($f$).


The emergence of fixed points can be demonstrated by a simple example.
Agent $A$'s diagonalization task can be formalized as
follows. Consider for the moment the action of diagonalization  on the
classical bit states. (Since the quantum bit states are merely a coherent superposition
thereof, the action of diagonalization on quantum bits is straightforward.)
Diagonalization effectively transforms the classical bit value $t$ into $f$ and
{\it vice versa.}
Recall that in equation
(\ref{el:halt}),  the state
$t$ has been identified
 with the halting state and the state $f$
with the non-halting
state. Since the halting state and the non-halting state exclude each
other,
$f,t$ can be identified with orthonormal basis vectors  in a
twodimensional vector space. Thus, the standard basis of
Cartesian coordinates can be chosen for a representation of $t$ and $f$;
i.e.,
\begin{equation}
t  \equiv
\left(
\begin{array}{c}
1 \\
0
 \end{array}
\right)
\mbox{ and }
f \equiv
\left(
\begin{array}{c}
0 \\
1
 \end{array}
\right) \quad .
\end{equation}

 The evolution representing diagonalization (effectively, agent
$A$'s task) can be expressed by the unitary operator $D$ by
\begin{equation}
D t  =  f \mbox{ and }
D f  =  t\quad .
\end{equation}
Thus, $D$ acts essentially as a ${\tt not}$-gate.
In the above state basis, $D$ can be represented as follows:
\begin{equation}
D=
\left(
\begin{array}{cc}
0 & 1\\
1 & 0
\end{array}
\right) \quad .
\end{equation}
$ D $ will be called {\em diagonalization} operator, despite the fact
that the only nonvanishing components are off-diagonal.


As has been pointed out earlier,
quantum information theory allows a coherent superposition
$ x_{\alpha ,\beta}  =\alpha t+\beta f $
of the
classical bit states $t$ and $f$.
$D$ acts on classical bits. It
has a
fixed point at the classical bit state
\begin{equation}
x^\ast :=x_{ {1\over \sqrt{2}},{1\over \sqrt{2}} }  ={t+f\over \sqrt{2}}
\equiv
{1\over \sqrt{2}} \left(
\begin{array}{c}
1 \\
1
 \end{array}
\right) \quad .
\end{equation}
$x^\ast$
does not give rise to inconsistencies \cite{deutsch91,svozil-paradox}.
If agent $A$ hands over the fixed point state
$x ^\ast $ to the diagonalization
operator $D$, the same state
$x^\ast $ is recovered.
Stated differently, as long as the output of the ``halting
algorithm'' to input $A(A)$ is $x^\ast$, diagonalization does not
change it. Hence, even if the (classically) ``paradoxical'' construction
of diagonalization is maintained, quantum theory does not give rise to a
paradox, because the quantum range of solutions is larger than the
classical one.
Therefore,
standard proofs of the recursive unsolvability of the halting problem
do not apply if agent $A$ is allowed a quantum bit. The consequences for
quantum recursion theory are discussed below.


It should be noted, however, that the fixed point quantum bit ``solution''
to the above halting problem is of not much practical help.
In particular, if one is interested in the ``classical'' answer whether
or not $A(A)$ halts,  then one ultimately has to perform an
irreversible measurement
on the fixed point state. This  causes a state reduction into the
classical states corresponding to $t$ and $f$.
Any single measurement will yield an indeterministic result.
There is a 50:50 chance that
the fixed point state will be either in $t$ or $f$, since
$P_t(
x ^\ast)=
P_f(
x^\ast )= {1\over 2}$.
Thereby, classical undecidability is recovered.

Another, less abstract, application for quantum information theory is
the handling of inconsistent information in databases.
Thereby,
two contradicting classical bits of information
$t$ and
$f $ are resolved by the quantum bit
$x^\ast =
{(t+f)/ \sqrt{2}}$.
Throughout the rest of the computation the coherence is maintained.
After the processing, the result is obtained by an irreversible
measurement. The processing of quantum bits, however, would require an
exponential
space overhead on classical computers in classical bit base \cite{feynman}.
Thus, in order to remain tractable,
the corresponding quantum bits should be implemented on
truly quantum universal computers.



As far as problem solving is concerned, classical bits are not much of an
advance. If a classical information is required, then quantum bits are not
better than probabilistic knowledge. With regards to the question of
whether or not a computer halts, for
instance, the ``solution''
is equivalent to the throwing of a fair coin.

Therefore, the advance of quantum recursion theory over classical
recursion theory is not so much classical problem solving but {\em the
consistent representation of statements} which would give rise to
classical paradoxes.

The above argument used the continuity of classical bit states as compared to the
two classical bit states for a construction of fixed points of the
diagonalization operator. One could proceed a step further and allow
{\em nonclassical diagonalization procedures}. Thereby, one could allow
the entire range of twodimensional unitary transformations
\cite{murnaghan}
\begin{equation}
U_2(\omega ,\alpha ,\beta ,\varphi )=e^{-i\,\beta}\,
\left(
\begin{array}{cc}
{e^{i\,\alpha }}\,\cos \omega
&
{-e^{-i\,\varphi }}\,\sin \omega
\\
{e^{i\,\varphi }}\,\sin \omega
&
{e^{-i\,\alpha }}\,\cos \omega
 \end{array}
\right)
 \quad ,
\label{e:quid3}
\end{equation}
where $-\pi \le \beta ,\omega \le \pi$,
$-\, {\pi \over 2} \le  \alpha ,\varphi \le {\pi \over 2}$, to act on
the quantum bit.
A typical example of a nonclassical operation on a quantum bit is
the ``square root of not'' gate
($
\sqrt{{\tt not}}
\sqrt{{\tt not}} =D$)
\begin{equation}
\sqrt{{\tt not}} =
{1 \over 2}
\left(
\begin{array}{cc}
1+i&1-i
\\
1-i&1+i
 \end{array}
\right)
\quad .
\end{equation}
Not all these unitary transformations have eigenvectors
associated with eigenvalues $1$ and thus fixed points.
Indeed, it is not difficult to see that only
unitary transformations of the form
\begin{equation}
\begin{array}{l}
[U_2(\omega ,\alpha ,\beta ,\varphi )]^{-1}\,\mbox{diag}(1, e^{i\lambda
}) U_2(\omega ,\alpha ,\beta ,\varphi )=\\
\quad   \quad \quad
\left(
\begin{array}{cc}
{{\cos \omega }^2} + {e^{i\,\lambda }}\,{{\sin \omega }^2}&
{{{
{-1 + {e^{i\,\lambda
}}\over 2}
e^{-i\,\left(\alpha +\varphi \right) }}\,
\, \sin (2\,\omega )}} \\
{ -1 + {e^{i\,\lambda }}\over 2}
 {{{e^{i\,\left(\alpha
+\varphi \right) }}\,
 \sin
(2\,\omega )}}&
{e^{i\,\lambda }}\,{{\cos \omega }^2} + {{\sin
\omega }^2}
 \end{array}
\right)
 \end{array}
\end{equation}
have fixed points.

Applying nonclassical operations on quantum bits with no fixed points
\begin{equation}
\begin{array}{l}
[U_2(\omega ,\alpha ,\beta ,\varphi )]^{-1}\,\mbox{diag}( e^{i\mu } ,
e^{i\lambda }) U_2(\omega ,\alpha ,\beta ,\varphi )=\\
\quad   \quad \quad
\left(
\begin{array}{cc}
  {e^{i\,\mu }}\,{{\cos (\omega )}^2} +
     {e^{i\,\lambda }}\,{{\sin (\omega )}^2}&
    {{{e^{-i\,\left( \alpha  + p \right) }\over 2}}\,
         \left( {e^{i\,\lambda }} - {e^{i\,\mu }} \right) \,\sin
(2\,\omega )}
       \\
{{{e^{i\,\left( \alpha  + p \right) }\over 2}}\,
        \left( {e^{i\,\lambda }} - {e^{i\,\mu }}  \right) \,\sin
(2\,\omega )}
       &{e^{i\,\lambda }}\,{{\cos (\omega )}^2} +
     {e^{i\,\mu }}\,{{\sin (\omega )}^2}
 \end{array}
\right)
 \end{array}
\end{equation}
with $\mu ,\lambda \neq n\pi$, $n\in {\Bbb N}_0$ gives rise to
eigenvectors which are not fixed points, but which acquire nonvanishing
phases $\mu , \lambda$ in the generalized diagonalization process.

\subsection{Quantum computation}

First attempts to quantize Turing machines
\cite{deutsch}
failed to identify any possibilities to go beyond Turing computability.
Recently, two independent proposals by
Calude and Pavlov et al. \cite{2002-cal-pav,ad-ca-pa},
as well as by Kieu et al. \cite{kieu-02,kieu-02a}.
Both proposals are not just mere quantized extensions of Turing machines,
but attempt to utilize very specific features and capacities
of quantum systems.

The question as to what might be considered the ``essence'' of quantum computation,
and its possible advantages over classical computation, has been the topic of
numerous considerations, both from a physical
(e.g., Ref.~\cite{ekerj96,pres-97,pres-ln,nielsen-book,galindo-02,mermin-04,eisert-wolf-04})
as well as from a computer science
(e.g., Ref.~\cite{Gruska,benn:97,Ozhigov:1997,bbcmw-01,cleve-99,fortnov-03}) perspective.
One advantage of quantum algorithms over classical computation
is the possibility to spread out, process, analyse and extract information
in multipartite configurations in coherent superpositions of classical states.
This can be discussed
in terms of quantum state identification problems
based on a proper partitioning of mutually orthogonal sets of states
\cite{svozil-2005-ko}.

The question arises whether or not it is possible
to encode equibalanced decision problems
into quantum systems, so that a single invocation
of a filter used for state discrimination suffices to obtain the result.
Certain kinds of propositions about
quantum computers exist which do not correspond to any classical statement.
In quantum mechanics information
can be coded in entangled multipartite systems in such a way that
information about the single quanta is not useful for (and even makes impossible)
a decryption of the quantum computation.


Alas,  not all decision problems
have a proper encoding
into some quantum mechanical system
such that their resources (computation time, memory usage) is bound by some
criterion such as polynomiality or even finiteness.
One ``hard'' problem is the parity of a binary function
of $k>1$ binary arguments
\cite{Farhi-98,bbcmw-01,Miao-2001,orus-04,stadelhofer-05}:
It is only possible to go from $2^k$ classical queries down to $2^k/2$
quantum queries, thereby gaining a factor of 2.

Another example is a type of halting problem:
Alice presents Bob a black box with input and output interfaces.
Bob's task is to find out whether an arbitrary function of $k$ bits encoded in the black box
will ever output "0."
As this configuration could essentially get as worse as a {\em busy beaver} problem
\cite{rado,chaitin-bb},
the time it takes for Alice's box to ever output a "0" may grow faster than
any recursive  function of $k$.

Functional recursion
and iterations may
represent an additional burden on efficiency.
Recursions may require
a space overhead to keep track of the computational path,
in particular if the recursion depth cannot be coded efficiently.
From this point of view,
quantum implementations of the Ackermann or the Busy Beaver functions,
to give just two examples,
may even be less efficient than classical implementations,
where an effective waste management can get rid of many bits;
in particular in the presence of a computable radius of convergence.


\section{Dualistic transcendence}


It is an entirely different and open question whether or not the human
or animal mind can ``outperform'' any Turing machine.
Almost everybody, including eminent researchers, has an opinion on this matter,
but not very much empirical evidence has been accumulated.
For example, Kurt G{\"{o}}del believed in the capacity
of the human mind to comprehend mathematical truth beyond provability
\cite{kreisel-80,casti-jimmy}.

Why should the mind outpace Church-Turing computability?
The question is strongly related to the eternal issue of dualism and the
relation of body and soul (if any), of the mind and its brain,
and of Artificial Intelligence.
Instead of giving a detailed review of the related spiritual, religious
and philosophical \cite{descartes-meditation} discussions,
we refer to a recent theory based on neurophysiologic processes
by Sir John Eccles \cite{popper-eccles,eccles:papal}.

Even more speculitatively,
Jack Sarfatti allegedly (in vain) built an ``Eccles Telegraph'' in the form of an
electric typewriter directed by a stochastic physical process
which might be believed to allow communication with spiritual entities.
It may not be considered totally unreasonable to
base a theory of miracles \cite{frank,jung1}
on the spontaneous occurrence of stochastic processes
\cite{greenberger-svozil}
which individually may be interpreted to be ``meaningful,''
although their occurrence is statistically insignificant.

Dualism has acquired a new model metaphor in {\em virtual realities}
\cite{svozil-nat-acad} and the associated artistic expressions which
have come with it  (see, e.g., Refs.~\cite{simula,totalrecall,permutationcity,Matrix}).
We might even go as far as stating that we are the ``dead on vacation''
\cite{godard-aa}, or incarcerated in a Cartesian prison
(cf. Descartes' Meditation I,9 of Ref.~\cite{descartes-meditation})\footnote{
Some time ago, I had a dream. I was in an old, possibly medieval, castle.
I walked through it. At times I had the feeling that there
was something ``out there,'' something so
inconceivable hidden that it was impossible to recognize.
Then suddenly I realized that there was something ``inside the walls:''
another, dual,
castle, quite as spacious as the one I was walking in, formed by the
inner side of what one would otherwise consider masonry.
There was a small opening, and I glanced through it. The inside looked
like a three-dimensional maze inhabited by dwarfs. The opening closed
again.}.

Computers are exactly such openings; doors of perception to hidden
universes.
In a computer-generated virtual environment the ``physical''
laws are deterministic and computable in the Church-Turing sense;
and yet this universe may not entirely be determined by the initial values and
the deterministic laws alone.
Dualism manifests itself in the two ``reality layers'' of the virtual reality
and the Beyond, as well as in the interface between them.
Through the interface, there can occur a steady flow of information back and forth
from and to the Beyond which is transcendental with respect to the
operational means available within the virtual reality.
Proofs of the recursive unsolvability of the halting problem or of
the rule inference problem,
for example,
break down due to the nonapplicability of
self-referential diagonal arguments in the transcendental Beyond.
This makes necessary a distinction between an extrinsic and an intrinsic representation
of the system \cite{svozil-94}.


\section{Verifiability}

Let us, in this final section, take up the thought expressed by Martin Davis in the first section;
and let us assume for a moment that some extraterrestrial visitors present
us a  device or ``oracle'' which
is purportedly capable to ``compute'' a non Church-Turing computable function.
In what follows we shall argue that we can do very little to verify such hilarious claims.
Indeed, this verification problem can be reduced to the induction problem,
which remains unsolved.


\subsection{Oracles in a black box}

However polished and suspicious the device looks,
for verification purposes
one may put it into a black box, whose only interfaces are
symbolic input and output devices, such as a keyboard and a digital display or printer.
The only important aspect of the black box is its input-output behaviour.

One (unrealistic) realization is a black box with an infinity machine stuffed into it.
The input and output ports of the infinity machine are directly connected to the input and
output interfaces of the black box.

The question we would like to clarify is this: how could observers by finite means know
that the black box represents an oracle doing something useful for us; in particular
computing a non Church-Turing computable function?

\subsection{Induction problem unsolved}

The question of verifiability of oracle computation can be related
to the question of how to differentiate a particular algorithm or more general
input-output behaviour from others.
In a very broad sense, this is the induction problem plaguing
inductive science from its very start.

Induction is ``bottom-up.'' It attempts to reconstruct certain postulated features
from events or the input-output performance of black boxes.
The induction problem, in particular algorithmic ways and methods
to derive certain outcomes or events from other (causally ``previous'')
events or outcomes via some kind of ``narratives'' such as physical theories,
still remains unsolved.
Indeed, in view of powerful formal incompleteness theorems, such as the halting problem,
the busy beaver function,
or the recursive unsolvability of the
rule inference problem, the induction problem is provable recursively unsolvable for
physical systems which can be reduced to, or at least contain, universal Turing machines.
The physical universe as we know it, appears to be of that kind
(cf. Refs.~\cite{svozil-93,svozil-unev}).

Deduction is of not much help with the oracle identification problem either.
It is ``top-down'' and postulates certain entities such as physical theories.
Those theories may just have been provided by another oracle,
they may be guesswork or just random pieces of data crap in a computer memory.
Deduction then derives empirical consequences from those theories.
But how could one possibly derive a non computable result if the only verifiable
oracles are merely Church-Turing computable?



\subsection{The conjecture on unverifiability beyond NP-completeness}

It is not totally unreasonable to speculate that
NP-completeness serves as a kind of boundary,
a demarcation line between operationally verifiable oracles
and nonverifiable ones.
For it makes no sense to consider propositions which cannot even be tractably verified.

\section{Outlook}

Presently the question of a proper formalization of the informal notion of
``algorithm'' seems to remain wide open.
With regards to discrete finite paper-and-pencil operations,
Church-Turing computability seems to be appropriate.
But if one takes into account physics,
in particular continuum mechanics and quantum physics,
the issues become less certain.
And if one is willing to include the full capacities of the human mind
with all its intuition and thoughtfulness,
any formalization appears highly speculative and inappropriate; at least for the time being,  but maybe forever.

%\bibliography{svozil}
%\bibliographystyle{osa}
%\bibliographystyle{apsrev}
%\bibliographystyle{unsrt}
%\bibliographystyle{plain}


\begin{thebibliography}{100}
\newcommand{\enquote}[1]{``#1''}
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\eprint}[2][]{\url{#2}}

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

\bibitem{brillouin1}
L.~Brillouin, \emph{Science and Information Theory}, second edition ed.
  (Academic Press, New York, 1962).

\bibitem{brillouin2}
L.~Brillouin, \emph{Scientific Uncertainty and Information} (Academic Press,
  New York, 1964).

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

\bibitem{rogers1}
H.~{Rogers, Jr.}, \emph{Theory of Recursive Functions and Effective
  Computability} (MacGraw-Hill, New York, 1967).

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

\bibitem{pit:90}
I.~Pitowsky, \enquote{The physical {C}hurch-{T}uring thesis and physical
  computational complexity,} Iyyun \textbf{39}, 81--99 (1990).

\bibitem{galindo-02}
A.~Galindo and M.~A. Martin-Delgado, \enquote{Information and computation:
  Classical and quantum aspects,} Reviews of Modern Physics \textbf{74},
  347--432 (2002). \eprint{quant-ph/0112105},
  \urlprefix\url{http://dx.doi.org/10.1103/RevModPhys.74.347}.

\bibitem{landauer:61}
R.~Landauer, \enquote{Irreversibility and Heat Generation in the Computing
  Process,} IBM Journal of Research and Development \textbf{3}, 183--191
  (1961). Reprinted in \cite[pp. 188-196]{maxwell-demon}.

\bibitem{landauer-67}
R.~Landauer, \enquote{Wanted: a physically possible theory of physics,} IEEE
  Spectrum \textbf{4}, 105--109 (1967).

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

\bibitem{landauer-87}
R.~Landauer, \enquote{Fundamental Physical Limitations of the Computational
  Process; an Informal Commentary,} Cybernetics Machine Group Newsheet
  (1/1/1987).

\bibitem{landauer-88}
R.~Landauer, \enquote{Dissipation and noise immunity in computation and
  communication,} Nature \textbf{335}, 779--784 (1988).

\bibitem{landauer-89}
R.~Landauer, \enquote{Computation, Measurement, Communication and Energy
  Dissipation,} in \emph{Selected Topics in Signal Processing}, S.~Haykin, ed.,
  p.~18 (Prentice Hall, Englewood Cliffs, NJ, 1989).

\bibitem{landauer}
R.~Landauer, \enquote{Information is physical,} Physics Today \textbf{44},
  23--29 (1991).

\bibitem{landauer-94}
R.~Landauer, \enquote{Zig-Zag Path to Understanding,} in \emph{Proceedings of
  the Workshop on Physics and Computation PHYSCOMP '94}, pp. 54--59 (IEEE
  Computer Society Press, Los Alamitos, CA, 1994).

\bibitem{landauer-95}
R.~Landauer, \enquote{Advertisement For a Paper {I} Like,} in \emph{On Limits},
  J.~L. Casti and J.~F. Traub, eds., p.~39 (Santa Fe Institute Report
  94-10-056, Santa Fe, NM, 1994).
  \urlprefix\url{http://www.santafe.edu/research/publications/workingpapers/94%
-10-056.pdf}.

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

\bibitem{rosen}
R.~Rosen, \enquote{Effective Processes and Natural Law,} in \emph{The Universal
  Turing Machine. A Half-Century Survey}, R.~Herken, ed., p. 523 (Kammerer \&
  Unverzagt, Hamburg, 1988).

\bibitem{kreisel}
G.~Kreisel, \enquote{A notion of mechanistic theory,} Synthese \textbf{29},
  11--16 (1974).

\bibitem{davis-58}
M.~Davis, \emph{Computability and Unsolvability} (McGraw-Hill, New York, 1958).

\bibitem{church30}
A.~Church, \enquote{A note on the {E}ntscheidungsprob1em,} Journal of Symbolic
  Logic \textbf{1}, 40--41 (1930).

\bibitem{church36}
A.~Church, \enquote{An unsolvable problem of elementary number theory,}
  American Journal of Mathematics \textbf{58}, 345--363 (1936).

\bibitem{godel1}
K.~G{\"{o}}del, \enquote{{\"{U}}ber formal unentscheidbare {S\"{a}}tze der
  {P}rincipia {M}athematica und verwandter {S}ysteme,} Monatshefte f{\"{u}}r
  Mathematik und Physik \textbf{38}, 173--198 (1931). {E}nglish translation in
  \cite{godel-ges1}, and in \cite{davis}.

\bibitem{turing-36}
A.~M. Turing, \enquote{On computable numbers, with an application to the
  {E}ntscheidungsproblem,} Proceedings of the London Mathematical Society,
  Series 2 \textbf{42 and 43}, 230--265 and 544--546 (1936-7 and 1937).
  Reprinted in \cite{davis}.

\bibitem{chaitin3}
G.~J. Chaitin, \emph{Algorithmic Information Theory} (Cambridge University
  Press, Cambridge, 1987).

\bibitem{calude:02}
C.~Calude, \emph{Information and Randomness---An Algorithmic Perspective}, 2nd
  ed. (Springer, Berlin, 2002).

\bibitem{bridgman}
P.~W. Bridgman, \enquote{A Physicist's Second Reaction to {M}engenlehre,}
  Scripta Mathematica \textbf{2}, 101--117, 224--234 (1934). Cf. R. Landauer
  \cite{landauer-95}.

\bibitem{bridgman52}
P.~W. Bridgman, \emph{The Nature of Some of Our Physical Concepts}
  (Philosophical Library, New York, 1952).

\bibitem{gandy1}
R.~O. Gandy, \enquote{Limitations to Mathematical Knowledge,} in \emph{Logic
  Colloquium '82}, D.~van Dalen, D.~Lascar, and J.~Smiley, eds. (North Holland,
  Amsterdam, 1982).

\bibitem{gandy2}
R.~O. Gandy, \enquote{Church's Thesis and Principles for Mechanics,} in
  \emph{The Kleene Symposium}, J.~Barwise, H.~J. Kreisler, and K.~Kunen, eds.
  (North Holland, Amsterdam, 1980).

\bibitem{popper-50i}
K.~R. Popper, \enquote{Indeterminism in Quantum Physics and in Classical
  Physics I,} The British Journal for the Philosophy of Science \textbf{1},
  117--133 (1950).

\bibitem{popper-50ii}
K.~R. Popper, \enquote{Indeterminism in Quantum Physics and in Classical
  Physics II,} The British Journal for the Philosophy of Science \textbf{1},
  173--195 (1950).

\bibitem{moore}
C.~D. Moore, \enquote{Unpredictability and undecidability in dynamical
  systems,} Physical Review Letters \textbf{64}, 2354--2357 (1990). Cf. Ch.
  Bennett, {\sl Nature}, {\bf 346}, 606 (1990),
  \urlprefix\url{http://link.aps.org/abstract/PRL/v64/p2354}.

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

\bibitem{casti:94-onlimits_book}
J.~L. Casti and J.~F. Traub (Santa Fe Institute, Santa Fe, NM, 1994). Report
  94-10-056,
  \urlprefix\url{http://www.santafe.edu/sfi/publications/Working-Papers/94-10-%
056.pdf}.

\bibitem{casti:96-onlimits}
J.~L. Casti and A.~Karlquist, \emph{Boundaries and Barriers. On the Limits to
  Scientific Knowledge} (Addison-Wesley, Reading, MA, 1996).

\bibitem{go-67}
E.~M. Gold, \enquote{Language identification in the limit,} Information and
  Control \textbf{10}, 447--474 (1967).
  \urlprefix\url{http://www.sciencedirect.com/science/article/B7MFM-4DX4964-C/%
2/cc2c59f85d26a52e92aad38d37790439}.

\bibitem{e-f-moore}
E.~F. Moore, \enquote{Gedanken-Experiments on Sequential Machines,} in
  \emph{Automata Studies}, C.~E. Shannon and J.~McCarthy, eds. (Princeton
  University Press, Princeton, 1956).

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

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

\bibitem{dvur-pul-svo}
A.~Dvure{\v{c}}enskij, S.~Pulmannov{\'{a}}, and K.~Svozil, \enquote{Partition
  Logics, Orthoalgebras and Automata,} Helvetica Physica Acta \textbf{68},
  407--428 (1995).

\bibitem{cal-sv-yu}
C.~Calude, E.~Calude, K.~Svozil, and S.~Yu, \enquote{Physical versus
  Computational Complementarity {I},} International Journal of Theoretical
  Physics \textbf{36}(7), 1495--1523 (1997). \eprint{quant-ph/9412004}.

\bibitem{svozil-ql}
K.~Svozil, \emph{Quantum Logic} (Springer, Singapore, 1998).

\bibitem{wright:pent}
R.~Wright, \enquote{The state of the pentagon. {A} nonclassical example,} in
  \emph{Mathematical Foundations of Quantum Theory}, A.~R. Marlow, ed., pp.
  255--274 (Academic Press, New York, 1978).

\bibitem{wright}
R.~Wright, \enquote{Generalized urn models,} Foundations of Physics
  \textbf{20}, 881--903 (1990).

\bibitem{svozil-2001-eua}
K.~Svozil, \enquote{Logical equivalence between generalized urn models and
  finite automata,} International Journal of Theoretical Physics \textbf{44},
  745--754 (2005). \eprint{quant-ph/0209136},
  \urlprefix\url{http://dx.doi.org/10.1007/s10773-005-7052-0}.

\bibitem{svozil-set}
K.~Svozil, \enquote{Set theory and physics,} Foundations of Physics
  \textbf{25}, 1541--1560 (1995).

\bibitem{sv-aut-rev}
K.~Svozil, \enquote{The {C}hurch-{T}uring Thesis as a Guiding Principle for
  Physics,} in \emph{Unconventional Models of Computation}, C.~S. Calude,
  J.~Casti, and M.~J. Dinneen, eds., pp. 371--385 (Springer, Singapore, 1998).

\bibitem{wagon1}
S.~Wagon, \emph{The Banach-Tarski paradox} (Cambridge University Press,
  Cambridge, 1986).

\bibitem{pitowsky-82}
I.~Pitowsky, \enquote{Resolution of the {E}instein-{P}odolsky-{R}osen and
  {B}ell paradoxes,} Physical Review Letters \textbf{48}, 1299--1302 (1982).
  Cf. N. D. Mermin, {\sl Physical Review Letters} {\bf 49}, 1214 (1982); A. L.
  Macdonald, {\sl Physical Review Letters} {\bf 49}, 1215 (1982); Itamar
  Pitowsky, {\sl Physical Review Letters} {\bf 49}, 1216 (1982),
  \urlprefix\url{http://dx.doi.org/10.1103/PhysRevLett.48.1299}.

\bibitem{svo-neufeld}
K.~Svozil and N.~Neufeld, \enquote{`Linear' chaos via paradoxical set
  decompositions,} Chaos, Solitons \& Fractals \textbf{7}(5), 785--793 (1996).
  \urlprefix\url{http://dx.doi.org/10.1016/0960-0779(95)00116-6}.

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

\bibitem{goldstein}
H.~Goldstein, \emph{Classical Mechanics. {S}econd Edition} (Addison-Wesley,
  Reading, MA, 1950,1980).

\bibitem{jackson}
J.~D. Jackson, \emph{Classical Electrodynamics}, 3rd ed. (John Wiley \& Sons,
  New York, 1999).

\bibitem{ein1}
A.~Einstein, \emph{Grundz{\"{u}}ge der {R}elativit{\"{a}}tstheorie}, 1st ed.
  (Vieweg, Braunschweig, 1956).

\bibitem{shaw}
R.~Shaw, Zeitschrift f{\"{u}}r Naturforschung \textbf{36a}, 80 (1981).

\bibitem{schuster1}
H.~G. Schuster, \emph{Deterministic Chaos} (Physik Verlag, Weinheim, 1984).

\bibitem{pit:96}
I.~Pitowsky, \enquote{Laplace's demon consults an oracle: The computational
  complexity of prediction,} Studies In History and Philosophy of Science Part
  B: Studies In History and Philosophy of Modern Physics \textbf{27}, 161--180
  (1996). \urlprefix\url{http://dx.doi.org/10.1016/1355-2198(96)85115-X}.

\bibitem{specker-ges}
E.~Specker, \emph{Selecta} (Birkh{\"{a}}user Verlag, Basel, 1990).

\bibitem{wang}
P.~S. Wang, \enquote{The undecidability of the existence of zeros of real
  elementary functions,} Journal of the ACM (JACM) \textbf{21}, 586--589
  (1974).

\bibitem{pr1}
M.~B. Pour-El and J.~I. Richards, \emph{Computability in Analysis and Physics}
  (Springer, Berlin, 1989).

\bibitem{bridges1}
D.~S. Bridges, \enquote{Constructive mathematics and unbounded operators---a
  reply to Hellman,} Journal of Philosophical Logic \textbf{28}(5) (1999).
  \urlprefix\url{http://dx.doi.org/10.1023/A:1004420413391}.

\bibitem{penrose:90}
R.~Penrose, \emph{The Emperor's New Mind: Concerning Computers, Minds, and the
  Laws of Physics} (Oxford University Press, Oxford, 1990).

\bibitem{gruenbaum:74}
A.~Gr{\"{u}}nbaum, \emph{Philosophical problems of space and time (Boston
  Studies in the Philosophy of Science, vol. 12)}, second, enlarged edition ed.
  (D. Reidel, Dordrecht/Boston, 1974).

\bibitem{thom:54}
J.~F. Thomson, \enquote{Tasks and supertasks,} Analysis \textbf{15}, 1--13
  (1954).

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

\bibitem{rucker}
R.~Rucker, \emph{Infinity and the Mind} (Birkh{\"{a}}user, Boston, 1982).
  Reprinted by Bantam Books, 1986.

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

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

\bibitem{hogarth2}
M.~Hogarth, \enquote{Non-{T}uring computers and non-{T}uring computability,}
  PSA \textbf{1}, 126--138 (1994).

\bibitem{beth-59}
E.~W. Beth, \emph{The Foundations of Metamathematics} (North-Holland,
  Amsterdam, 1959).

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

\bibitem{weyl:49}
H.~Weyl, \emph{Philosophy of Mathematics and Natural Science} (Princeton
  University Press, Princeton, 1949).

\bibitem{deutsch91}
D.~Deutsch, \enquote{Quantum mechanics near closed timelike lines,} Physical
  Review D \textbf{44}, 3197--3217 (1991).
  \urlprefix\url{http://dx.doi.org/10.1103/PhysRevD.44.3197}.

\bibitem{svozil-paradox}
K.~Svozil, \enquote{Consistent use of paradoxes in deriving contraints on the
  dynamics of physical systems and of no-go-theorems,} Foundations of Physics
  Letters \textbf{8}(6), 523--535 (1995).

\bibitem{ord-kieu-03}
T.~Ord and T.~D. Kieu, \enquote{The Diagonal Method and Hypercomputation,}
  (2003). \eprint{math.LO/0307020}.

\bibitem{feynman}
R.~P. Feynman, \enquote{Simulating physics with computers,} International
  Journal of Theoretical Physics \textbf{21}, 467--488 (1982).

\bibitem{murnaghan}
F.~D. Murnaghan, \emph{The Unitary and Rotation Groups} (Spartan Books,
  Washington, D.C., 1962).

\bibitem{2002-cal-pav}
C.~S. Calude and B.~Pavlov, \enquote{Coins, Quantum Measurements, and
  {T}uring's Barrier,} Quantum Information Processing \textbf{1}, 107--127
  (2002). \eprint{quant-ph/0112087},
  \urlprefix\url{http://arxiv.org/abs/quant-ph/0112087}.

\bibitem{ad-ca-pa}
V.~A. Adamyan and B.~S.~P. Cristian S.~Calude, \enquote{Transcending the Limits
  of {T}uring Computability,}  (1998). \eprint{quant-ph/0304128},
  \urlprefix\url{http://arxiv.org/abs/quant-ph/0304128}.

\bibitem{kieu-02}
T.~D. Kieu, \enquote{Quantum Algorithm for {H}ilbert's Tenth Problem,}
  International Journal of Theoretical Physics \textbf{42}, 1461--1478 (2003).
  \eprint{quant-ph/0110136},
  \urlprefix\url{http://arxiv.org/abs/quant-ph/0110136}.

\bibitem{kieu-02a}
T.~D. Kieu, \enquote{Computing the Noncomputable,} Contemporary Physics
  \textbf{44}, 51--71 (2003). \eprint{quant-ph/0203034},
  \urlprefix\url{http://arxiv.org/abs/quant-ph/0203034}.

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

\bibitem{pres-97}
J.~Preskill, \enquote{Quantum Computing: Pro and Con,} Proceedings of the Royal
  Society (London) A \textbf{454}, 469--486 (1998). \eprint{quant-ph/9705032},
  \urlprefix\url{http://dx.doi.org/10.1098/rspa.1998.0171}.

\bibitem{pres-ln}
J.~Preskill, \enquote{Quantum Computation,} Lecture notes,
  \eprint{quant-ph/9705032},
  \urlprefix\url{http://www.theory.caltech.edu/~preskill/ph219/index.html}.

\bibitem{nielsen-book}
M.~A. Nielsen and I.~L. Chuang, \emph{Quantum Computation and Quantum
  Information} (Cambridge University Press, Cambridge, 2000).

\bibitem{mermin-04}
N.~D. Mermin, \enquote{Lecture Notes on Quantum Computation,}   (2002-2004).
  \urlprefix\url{http://people.ccmr.cornell.edu/~mermin/qcomp/CS483.html}.

\bibitem{eisert-wolf-04}
M.~W. J.~Eisert, \enquote{Quantum computing,} in \emph{Handbook Innovative
  Computing}, A.~Zomaya, G.~Milburn, J.~Dongarra, D.~Bader, R.~Brent,
  M.~Eshaghian-Wilner, and F.~Seredynski, eds., pp. 281--283 (Springer, Berlin,
  Heidelberg, New York, 2004). \eprint{quant-ph/0401019}.

\bibitem{Gruska}
J.~Gruska, \emph{Quantum Computing} (McGraw-Hill, London, 1999).

\bibitem{benn:97}
C.~H. Bennett, E.~Bernstein, G.~Brassard, and U.~Vazirani, \enquote{Strengths
  and Weaknesses of Quantum Computing,} SIAM Journal on Computing \textbf{26},
  1510--1523 (1997). \eprint{quant-ph/9701001},
  \urlprefix\url{http://dx.doi.org/10.1137/S0097539796300933}.

\bibitem{Ozhigov:1997}
Y.~Ozhigov, \enquote{Quantum Computer Can Not Speed Up Iterated Applications of
  a Black Box,}  (1997). \eprint{quant-ph/9712051}.

\bibitem{bbcmw-01}
R.~Beals, H.~Buhrman, R.~Cleve, M.~Mosca, and R.~de~Wolf, \enquote{Quantum
  Lower Bounds by Polynomials,} Journal of the ACM \textbf{48}, 778--797
  (2001). \eprint{quant-ph/9802049},
  \urlprefix\url{http://dx.doi.org/10.1145/502090.502097}.

\bibitem{cleve-99}
R.~Cleve, \enquote{An Introduction to Quantum Complexity Theory,} in
  \emph{Collected Papers on Quantum Computation and Quantum Information
  Theory}, C.~Macchiavello, G.~Palma, and A.~Zeilinger, eds., pp. 103--127
  (World Scientific, Singapore, 2000). \eprint{quant-ph/9906111}.

\bibitem{fortnov-03}
L.~Fortnow, \enquote{One complexity theorist's view of quantum computing,}
  Theoretical Computer Science \textbf{292}, 597--610 (2003).
  \urlprefix\url{http://dx.doi.org/10.1016/S0304-3975(01)00377-2}.

\bibitem{svozil-2005-ko}
K.~Svozil, \enquote{Characterization of quantum computable decision problems by
  state discrimination,} in \emph{AIP Conference Proceedings}, A.~Khrennikov,
  ed., p. in print (American Institute of Physics, Melville, NY, 2005).
  \eprint{quant-ph/0505129}, \urlprefix\url{in print}.

\bibitem{Farhi-98}
E.~Farhi, J.~Goldstone, S.~Gutmann, and M.~Sipser, \enquote{Limit on the Speed
  of Quantum Computation in Determining Parity,} Physical Review Letters
  \textbf{81}, 5442--5444 (1998). \eprint{quant-ph/9802045},
  \urlprefix\url{http://dx.doi.org/10.1103/PhysRevLett.81.5442}.

\bibitem{Miao-2001}
X.~Miao, \enquote{A polynomial-time solution to the parity problem on an {NMR}
  quantum computer,}  (2001). \eprint{quant-ph/0108116}.

\bibitem{orus-04}
R.~Orus, J.~I. Latorre, and M.~A. Martin-Delgado, \enquote{Systematic Analysis
  of Majorization in Quantum Algorithms,} European Physical Journal D
  \textbf{29}, 119--132 (2004). \eprint{quant-ph/0212094},
  \urlprefix\url{http://dx.doi.org/10.1140/epjd/e2004-00009-3}.

\bibitem{stadelhofer-05}
R.~Stadelhofer, D.~Suterand, and W.~Banzhaf, \enquote{Quantum and classical
  parallelism in parity algorithms for ensemble quantum computers,} Physical
  Review A \textbf{71}, 032,345 (2005). \eprint{quant-ph/0112105},
  \urlprefix\url{http://dx.doi.org/10.1103/PhysRevA.71.032345}.

\bibitem{rado}
T.~Rado, \enquote{On Non-Computable Functions,} The Bell System Technical
  Journal \textbf{XLI(41)}(3), 877--884 (1962).

\bibitem{chaitin-bb}
G.~J. Chaitin, \enquote{Computing the Busy Beaver Function,} in \emph{Open
  Problems in Communication and Computation}, T.~M. Cover and B.~Gopinath,
  eds., p. 108 (Springer, New York, 1987). Reprinted in \cite{chaitin2}.

\bibitem{kreisel-80}
G.~Kreisel, Biographical memoirs of Fellows of the Royal Society \textbf{26},
  148 (1980). Corrections {\it Ibid.} {\bf 27}, 697; {\it ibid.} {\bf 28}, 718.

\bibitem{casti-jimmy}
J.~L. Casti and W.~Depauli-Schimanovich, \emph{G�del: A Life of Logic}
  (Perseus, Cambridge, MA, 2000).

\bibitem{descartes-meditation}
R.~Descartes, \emph{Meditation on First Philosophy} (1641).
  \urlprefix\url{http://oregonstate.edu/instruct/phl302/texts/descartes/medita%
tions/meditations.html}.

\bibitem{popper-eccles}
K.~R. Popper and J.~C. Eccles, \emph{The Self and Its Brain} (Springer, Berlin,
  Heidelberg, London, New York, 1977).

\bibitem{eccles:papal}
J.~C. Eccles, \enquote{The Mind-Brain Problem Revisited: The Microsite
  Hypothesis,} in \emph{The Principles of Design and Operation of the Brain},
  J.~C. Eccles and O.~Creutzfeldt, eds., p. 549 (Springer, Berlin, 1990).

\bibitem{frank}
P.~Frank, \emph{Das Kausalgesetz und seine Grenzen} (Springer, Vienna, 1932).
  English translation in Ref.~\cite{franke}.

\bibitem{jung1}
C.~G. Jung, \enquote{Synchronizit{\"{a}}t als ein {P}rinzip akausaler
  {Z}usammenh{\"{a}}nge,} in \emph{Naturerkl{\"{a}}rung und Psyche}, C.~G. Jung
  and W.~Pauli, eds. (Rascher, Z{\"{u}}rich, 1952).

\bibitem{greenberger-svozil}
D.~M. Greenberger and K.~Svozil, \enquote{A quantum mechanical look at time
  travel and free will,} in \emph{Between Chance and Choice}, H.~Atmanspacher
  and R.~Bishop, eds., pp. 293--308 (Imprint Academic, Thorverton, 2002).

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

\bibitem{simula}
D.~F. Galouye, \emph{Simulacron 3} (1964).

\bibitem{totalrecall}
\enquote{Total Recall,}  (1990). Movie, Director Paul Verhoeven, USA. 113
  minutes. {E}nglish, budget of US\$65 million.

\bibitem{permutationcity}
G.~Egan, \emph{Permutation City} (1994).

\bibitem{Matrix}
\enquote{The Matrix,}  (1999). Movie, Directors Andy Wachowski and Larry
  Wachowski, USA. 136 min. {E}nglish, budget of US\$80 million.

\bibitem{godard-aa}
\enquote{{\'{A}} bout de souffle (aka Breathless,}  (1960). Movie, Director
  Jean-Luc Godard. 87 min {F}rench.

\bibitem{svozil-94}
K.~Svozil, \enquote{Extrinsic-intrinsec concept and complementarity,} in
  \emph{Inside versus Outside}, H.~Atmanspacker and G.~J. Dalenoort, eds., pp.
  273--288 (Springer-Verlag, Heidelberg, 1994).

\bibitem{svozil-unev}
K.~Svozil, \enquote{Undecidability everywhere?} in \emph{Boundaries and
  Barriers. On the Limits to Scientific Knowledge}, J.~L. Casti and
  A.~Karlquist, eds., pp. 215--237 (Addison-Wesley, Reading, MA, 1996).

\bibitem{godel-ges1}
K.~G{\"{o}}del, in \emph{Collected Works. Publications 1929-1936. Volume {I}},
  S.~Feferman, J.~W. Dawson, S.~C. Kleene, G.~H. Moore, R.~M. Solovay, and
  J.~van Heijenoort, eds. (Oxford University Press, Oxford, 1986).

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

\bibitem{chaitin2}
G.~J. Chaitin, \emph{Information, Randomness and Incompleteness}, 2nd ed.
  (World Scientific, Singapore, 1990). This is a collection of G. Chaitin's
  early publications.

\bibitem{franke}
P.~Frank and R.~C. (Editor), \emph{The Law of Causality and its Limits (Vienna
  Circle Collection)} (Springer, Vienna, 1997).

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

\end{thebibliography}

\end{document}
