\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}