\documentclass[pra,amsfonts,preprint,showkeys]{revtex4} %\documentclass[pra,showpacs,showkeys,amsfonts]{revtex4} %\usepackage[T1]{fontenc} %\usepackage{graphicx} %\documentstyle[amsfonts]{article} %\RequirePackage{times} %\RequirePackage{courier} %\RequirePackage{mathptm} %\renewcommand{\baselinestretch}{1.3} \begin{document} %\sloppy \title{Quantum randomness and value indefiniteness} \author{Cristian S. Calude\footnote{Work done at the University of Technology Vienna: the support of the Institute for Theoretical Physics is gratefully acknowledged.}} \email{cristian@cs.auckland.ac.nz} \homepage{http://www.cs.auckland.ac.nz/~cristian/} \affiliation{Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand} \author{Karl Svozil} \email{svozil@tuwien.ac.at} \homepage{http://tph.tuwien.ac.at/~svozil} \affiliation{Institute for Theoretical Physics, University of Technology Vienna, Wiedner Hauptstra\ss e 8-10/136, A-1040 Vienna, Austria} \begin{abstract} As computability implies value definiteness, certain sequences of quantum outcomes cannot be computable. \end{abstract} %\pacs{03.67.-a,05.40.Ca,05.45.Tp} \keywords{Quantum information, quantum randomness, time series analysis, noise} \maketitle \thispagestyle{empty} \section{Conceptualisation} It certainly would be fascinating to pinpoint the time of the emergence of the notion that certain quantum processes, such as the decay of an excited quantum state, occurs principally and irreducibly at random; and how long it took to become the dominant way of thinking about them after almost two centuries of quasi-rationalistic dominance. Bohr's and Heisenberg's influence has been highly recognised and has prevailed, even against the strong rationalistic and philosophic objections raised by, for instance, by Einstein and Schr\"odinger \cite{jammer:66,jammer1}. Of course, one of the strongest reasons for this growing acceptance of quantum randomness has been the factual inability to go ``beyond'' the quantum in any manner which would encourage new phenomenology and might result in any hope for a progressive quasi-classical research program \cite{lakatosch}. Here we intend to discuss quantum randomness and its connection with quantum value indefiniteness. Bell \cite{bell-66,bell,bell-87,pitowsky-89a}, Kochen and Specker (KS) \cite{kochen1}, as well as Greenberger, Horne and Zeilinger (GHZ) \cite{ghz,ghsz,panbdwz} contributed to the evidence that the mere concept of coexistence of certain elements of physical reality \cite{epr} results in a complete contradiction. In this view, speculations about the ``reasons'' for certain outcomes of experiments are necessarily doomed; just because of the simple fact that any such rational reason is provably (by contradiction) impossible. An attempt is made here to clearly spell out the issues and problems involved in considering randomness, both with regard to the occurrence of single events, as well as their combination into time series. We wish to state from the beginning that we attempt to have no bias or preference for or against randomness. While to us it seems obvious that any claim of non-randomness has to be confronted with the factual inability to produce any satisfactory theory that goes beyond the quantum, especially in view of the known no-go theorems by Bell, KS and GHZ and others referred to above, it is also advisable to keep all options open and carefully study the types of randomness involved, and their possible ``origins,'' if any. Usually, the random outcome of certain quantum physical events seems to be axiomatically postulated from the onset; an assumption which can be also based on elementary principles \cite{zeil-99,zeil-bruk-02}. Here we argue that actually we can go further and infer some properties of quantum randomness --- including the absence of effective global correlations --- from the impossibility of value definiteness of certain quantum mechanical observables. \subsection{Difficulties}%Scenarios} Consider, as two extreme cases, the binary expansion $\pi_1\pi_2\pi_3\ldots \pi_i \pi_{i+1} \ldots$ of pi, an ideal circle's ratio of the circumference to its diameter, starting from, say, the 571113th billion prime number place onwards, and compare it to a sequence generated by quantum coin tosses $x_1x_2x_3\ldots x_i x_{i+1} \ldots$ \cite{svozil-qct,zeilinger:qct,Cris04}. How could anyone possibly see a difference with respect to their (non-)stochasticity? For all practical purposes, the sequences will appear structurally identically from a stochastic point of view, and heuristically random. For example, both are unknown to be Borel normal; i.e., all finite sub-sequences $y_1y_2y_3\ldots y_N$ might be contained in them with the expected frequencies. %, and seem to satisfy this criterium for finite sub-sequences. Indeed, it is not unreasonable to speculate that the pi sequence might be immune to all statistical and algorithmic tests of randomness but one: a test against the assumption that it is the binary expansion of pi, starting from the 571113th billion prime number place onwards. %{\bf But because of the more practical constraints on real-word %computation, even the production of the first bit of the pi sequence % appears to be un-feasible, i.e.,computing it seems to be hard. ???} Another obstacle for the physical conceptualisation of quantum randomness and its operationalisation in terms of physical entities originates in the formalism upon which such endeavours have to be based. The formal incompleteness and independence discovered by G\"odel, Tarski, Turing, Chaitin and others essentially renders algorithmic proofs of randomness hopeless. We shall discuss these issues below, but we just note that, as an example, verification of any ``law'' describable by $k$ symbols requires times exceeding any computable function of $k$ [such as the Ackermann function $A(k)$] and could in general take also that long to be falsified. Thus, the proof of any absence of lawful behaviour seems provable impossible. Randomness is an asymptotic property, that is, it is unaffected by finite variations. This makes testing randomness extremely difficult: one has to find finite tests capable of distinguishing an infinite behaviour. %Finally, the axioms for quantum randomness are fairly weak (see %section~I.C): apparently, they don't allow to prove many %mathematically consequences! We may pose the question: do we %need to postulate them? \subsection{Scenarios} %Single events and sequences generated by single events} Quantum randomness appears to occur in two different scenarios: (i) the complete impossibility to predict or explain the occurrence of certain {\em single} events and measurement outcomes from any kind of operational causal connection. The hidden ``parameter models'' for the quantum phenomena which have been proposed so far do not provide more insight for the predictions of intrinsic observers embedded in the system; and (ii) the concatenation of such single quantum random events forms sequences of random bits which can be expected to be equivalent stochastically to white noise. White noise carries the least correlations, as the occurrence of a particular bit value in a binary expansion does not depend on previous or future bits of that expansion \cite{gard-78}. These different ways to encounter randomness --- single random events and a concatenation thereof --- should be perceived very differently: in the single event case, the outcome occurs in the highly complex environment of the quantum and its measurement apparatus, which is thereby ``folded'' into a single bit. Repetition of the experiment does not increase the complexity of the combined system of the quantum--measurement apparatus, whose repetitive properties and behaviours are ``unfolded'' in repeated experiments. Hence, possible biases against statistical tests may be revealed easier by considering sequences of single random outcomes. In this note we shall thus concentrate on this second. \subsection{Axioms for quantum randomness and degrees of randomness}%Algorithmic information of random sequences} In what follows, we will assume the standard two ``axioms'' for quantum randomness~\cite{jauch}: \begin{itemize} \item The single outcome from which quantum random sequences are formed, occurs unbiased; i.e., for the $i$th outcome, there is a 50:50 probability for either 0 or 1: \begin{equation} \begin{array}{l} \textrm{Prob}(x_i=0) = \textrm{Prob}(x_i=1) ={1\over 2}\raisebox{0.5ex}{.} \end{array} \end{equation} \item There is a total independence of previous history, such that no correlation exists between $x_i$ and previous or future outcomes. This means that the system carries no memories of previous or expectations of future events. All outcomes are temporally ``isolated'' and free from control, influence and determination. They are both unbiased and self-contained. \end{itemize} Assume that we have a quantum experiment (using light, for example: a photon generated by a source beamed to a semitransparent mirror is {\it ideally} reflected or transmitted with 50 per cent chance) which at each stage produces a quantum random bit, and we assume that this experiment is run for ever generating an infinite binary sequence: \begin{equation} \label{qrand} X =x_1x_2x_3\cdots x_i \cdots \end{equation} In this scenario, the first axiom shows that the limiting frequency of 0 and 1 in the sequence $X$ is $1/2$. Locally, we might record significant deviations, i.e., $X$ may well start with a thousand of 1's, but in the limit these discrepancies disappear. The ``lack of correlations'' postulated above is more difficult to understand and may easily lead to misunderstandings, hence errors. First, {\it finite correlations} will always exist, because of the asymptotic nature of ``randomness''. Secondly, even {\it infinite correlations} cannot be eliminated because they have been proven to exist in {\it every infinite sequence}; for example Ramsey-type correlations, see \cite{calude:02}. So, what type of correlations should be prohibited? There are many possible choices, but the ones which come naturally to mind are ``effectively computable defined correlations.'' In other terms, correlations --- finite or infinite --- which can be detected in an effective/algorithmic way, should be excluded. Once the nature of the two axioms of randomness has been clarified, we can ask ourselves whether we need both axioms, that is, whether the axioms are {\it independent}. The answer is {\it affirmative} and here is the proof. %But there exist sequences which have no known correlations %(despite ``global ones''), yet are computable. An example of a binary sequence which satisfies the first axiom, but not the second axiom is Champernowne's sequence $0100011011000001010011 \cdots 1110000 \cdots$, which is just the concatenation of all binary strings in quasi-lexicographical order. In this sequence 0 and 1 have limiting frequency $1/2$ (even, more, each string of length $n$ has limiting frequency exactly $1/2^{n}$), but, of course, this sequence is computable, so it contains infinitely many finite and infinite correlations. It is possible to transform a sequence $Z = z_{1}z_{2}\cdots$ with no correlations and limiting frequency of 0's (and 1's) exactly $1/2$ into a sequence which has no infinite correlations, but the limiting frequency of 0's is $2/3$ and the limiting frequency of 1's is $1/3$: replace in $Z$ every 0 by 001, and every 1 by 100. This new sequence will have ``weak local correlations'' --- for example 0010 has to be followed by 01 --- but those correlations are not global. We stress the fact that we are interested in ``theoretical'' sequences (\ref{qrand}) produced by an ideal quantum experiment generating randomness, not the specific results of a particular quantum device like {\it Quantis}, \cite{Quantis}. Real devices are prone to real-world imperfections, even watered-down by various unbiasing methods, see \cite{Cris04}; however, our results apply in the limit to sequences generated by devices like {\it Quantis} (see \cite{Cris04,calude-dinneen05}). What is the degree of ``randomness'' of the resulting white noise sequence? Theoretically there are a few possibilities, ranging from ``total randomness'' expressed mathematically by saying that the sequence is algorithmically incompressible or algorithmically random,\cite{calude:02} to weaker and weaker possibilities: Turing-uncomputable of various degrees, but not algorithmically incompressible, Turing-computable, easy Turing-computable. Which of these possibilities actually does occur? \section{Main results} \subsection{Quantum value indefiniteness} In classical physics, omniscience manifests itself in the implicit assumption that it is possible to know all physical properties, or to put it in the context of the Einstein, Podolsky and Rosen argument \cite{epr}, all ``elements of physical reality'' are definite. Classical realism assumes that these definite physical properties exist without being experienced by any finite mind \cite{stace}, that it would not matter whether or not a particular physical observable is measured or not; and that the outcome of any such measurement is independent of whatever is measured alongside with it; that is, of its context. To state it pointedly: all classical physical observables exist simultaneously and independent of observation. Complementarity expresses the impossibility to measure two observables, such as the spin states of two spin-${1\over 2}$ particles along orthogonal directions, with arbitrary precision. But, as equivalent \cite{svozil-2001-eua} generalised urn \cite{wright} or automaton models \cite{svozil-ql} demonstrate, complementarity does not necessarily imply value indefiniteness. There still could exist enough two-valued states on the associated propositional structures to allow a faithful embedding into a Boolean algebra associated with classical physical systems. Formally, value indefiniteness manifests itself in the ``scarcity'' or non-existence of two-valued states --interpretable as classical truth assignments -- on all or even merely a finite set of physical observables. This is known as the Kochen-Specker theorem \cite{kochen1} (for related results, see Refs.~\cite{ZirlSchl-65,Alda,Alda2,kamber64,kamber65}). Very similar conclusions can be drawn from the impossibility to enumerate tables of results associated with Bell-type experiments in a consistent way: no such tables could possibly reproduce the non-classical quantum correlations \cite{peres222,krenn,svozil-krenn}. Confronted with the impossibility to consistently assign globally defined observables, one may assume, in an attempt to maintain realism, that the outcome of a particular experiment depends on the other observables which are co-measured simultaneously (Bell~\cite{bell-66}, Sec.~5). This assumption is called ``context dependence.'' Alternatively, one may depart from classical omniscience and assume that an elementary two-state system can carry at least a single bit, and nothing more. The context enters in the form of the maximal operator, such that all other co-measurable operators are functions thereof. If a particle can be prepared only to be in a single context, then the question quite naturally arises why the measurement of a different context not matching the preparation context yields any outcome at all. Pointedly stated, it is amazing that {\it for non-matching contexts there is an outcome rather than none}. We note that only under these circumstances, quantum randomness manifests itself, because if the preparation and the measurement contexts match, the measurement just renders the definite outcome associated with the state in which the particle was prepared. In this non-contextual view, quantum value indefiniteness expresses the fact that no deterministic, (pre-) defined non-contextual element of physical reality could consistently exist for observables in contexts not matching the preparation context. This is true also if we assume some form of ``context translation'' which may introduce stochasticity through some mechanism of interaction with the measurement device. \subsection{From value indefiniteness to Turing-uncomputability} Thus, we conclude, {\it no non-contextual, deterministic computation could exist which yields such a measurement outcome}. If one insists on some form of agent producing the outcome, then this agent must perform like an erratic gambler rather than a faithful executor of a deterministic algorithm. Restated differently, suppose a quantum sequence hitherto considered would be computable. In this case, the computations involved would produce a definite number associated with a definite outcome, which in turn could be associated with a definite element of physical reality. Yet we know that for Hilbert spaces of dimension greater than two, the assumption of value definiteness of all possible observables results in a complete contradiction. Hence, one is forced to conclude that {\it the assumption of computability has to be given up, and hence the sequence $X$ in (\ref{qrand}) is Turing-uncomputable.} Because the class of computable sequences is countable, with probability one (even, constructively, with probability one, see \cite{calude:02}) every sequence is Turing-uncomputable. Our result stated above is much stronger: {\it no sequence $X$ in (\ref{qrand}) is Turing-computable}. In particular, it says that any sequence $X$ cannot contain only 0's, it cannot represent in binary the digits of the binary expansion of pi or the Champernowne sequence. More, no sequence $X$ can coincide with a pseudo-random sequence (i.e., sequence obtain via Turing machine program), a fact alluded to almost 50 years ago by John von Neumann: ``Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin''. \subsection{White noise and algorithmic incompressibility} Uncomputability is a strong property, but it does not necessarily imply algorithmically incompressibility. Is a sequence $X$ more similar to the typical Turing-uncomputable sequence given by the classification of Turing programs in halting or non-halting, \begin{equation} \label{hseq} H =h_1h_2h_3\cdots h_i \cdots, \end{equation} or to the sequence of bits of a Chaitin Omega number, the halting probability: \begin{equation} \label{omega} \Omega =\omega_1 \omega_2 \omega_3\cdots \omega_i \cdots ? \end{equation} The sequence $H$ is defined by assigning to $h_{i}$ the value 1 if the $i$th Turing program (in some systematic enumeration) halts, and the value 0 in the opposite case. The sequence $\Omega$ is obtained by working with self-delimiting Turing machines (i.e. machines with prefix-free domains) by the formula: \[\Omega = \sum_{p {\footnotesize \mbox{ halts}}} 2^{-|p|},\] where $|p|$ denotes the length (in bits) of the program $p$ (see more in \cite{calude:02}). Both $H$ and $\Omega$ are Turing-uncomputable. The sequence $H$ is Turing-uncomputable, but it is also not algorithmic incompressible. A reason is the fact that we can effectively compute infinitely many exact values of $H$ by explicitly constructing infinitely many halting (or, non-halting) programs. The sequence $\Omega$ is algorithmic incompressible. Both $H$ and $\Omega$ can solve the famous Halting Problem: we need the first $2^{n}$ bits of $H$ to solve the Halting Problem for programs $p$ of length $|p| \le n$, but we need no more than the first $n$ bits of $\Omega$ to solve the same problem. The prefixes of $\Omega$ encode the same amount of information as the prefixes of $H$, but in an exponentially more compressed way. It is not difficult to see that the argument presented below to show that $X$ is Turing-uncomputable can be adapted to prove that {\it every infinite sub-sequence of $X$ is Turing-uncomputable.} More formally, {\it there is no partially computable function $\varphi$ defined on an infinite set of positive integers such that if $\varphi (n)$ is defined, then $\varphi (n) = x_{n}$}. This property is called {\it bi-immunity} in the theory of computability, see Odiffredi \cite{odi:99}. This property is shared by $\Omega$, but not by $H$. \subsection{Some consequences} We discuss some simple consequences of the above result. First, no Turing machine can enumerate/compute any sub-sequence of $X$. This means that every given Turing machine can compute only finitely many exact bits of $X$ in the same way that every given Turing machine can compute only finitely many exact bits of $\Omega$ (in contrast with $H$). Similarly, any formal system (ZFC, for example) will be able to ``prove'' only finitely many exact values of the sequence $X$. Secondly, the sequence $X$ is {\it not predictable}. The most clear intuition people have about randomness is unpredictability: the bits of a ``random'' sequence should be such that one cannot predict the next bit even if one knows all preceding bits. The simplest way to model this phenomenon (see other models in \cite{DH}) is to consider predictions of the $(n+1)$th element of the sequence when one knows the first $n$ elements. The corresponding model is to accept as {\it predictor} a partial computable function $Pred$ defined on a subset of the prefixes of $X$ with 0-1 values. If $Pred(w)= z$ and $z= x_{|w|+1}$ we say that the bit $z$ was predicted from $w$. % x_{1}x_{2}\cdots x_{n} % x_{n+1}$ was predicted from the bits $x_{1}x_{2}\cdots x_{n}$. Does there exist a predictor $Pred$ predicting infinitely many bits of $X$? The answer is clearly negative: from $Pred$ we can construct a partially computable function $\varphi$ capable of enumerating infinitely many values of $X$ just by enumerating the domain of $Pred$ and each time we get $Pred(w)= z$ and $z= x_{|w|+1}$, then we put $\varphi (|w|)=z$. This leads to a contradiction. Thirdly, a more general result can be proved: {\it there are no effective global (infinite) correlations between the bits of $X$.} One way to formalise this idea is to consider all possible properties between the prefixes of $X$ that can be determined in an effective way. We can prove the following result: {\it Every infinite relation of the form $G =\{(u,v)\mid uv \mbox{ is a prefix of } X\}$ is not computably enumerable.} Indeed, from $G$ we can construct the partial function $\varphi$ as follows: to the pair $(u,v)\in G, v = v_{1}v_{2}\cdots v_{m}$ we associate the following values of $\varphi$: $\varphi (|u| + i-1)= v_{i}, i= 1, \ldots ,m. $ The function $\varphi$ is correctly defined because of the condition specified in the definition of $G$; it shows that one can effectively enumerate infinitely many bits of $X$, a contradiction. \section{Summary and discussion} We have argued that, because of the value indefiniteness encountered in quantum mechanics, there cannot exist deterministic computations ``yielding'' infinitely many individual quantum random bits. We have further exploited value indefiniteness formally by stating the consequences in terms of Turing-uncomputability for sequences of such quantum random bits. No effectively computable global correlations can exist between the bits of a quantum random sequence. We have also examined, in a theoretical manner, the role of the second axiom of quantum randomness. The first axiom, stochasticity, seems more difficult to be studied from a purely theoretical point of view --- of course, it will be extremely interesting to have results in this direction --- but can be experimentally approached (for example, with the help of statistically significant samples produced by {\it Quantis}). Finally, we note that the result presented in this note says nothing about the possibility of extracting quantum bits from the quantum source of randomness, which, one might hope, could enhance the power of ``real'' computation. Some impossibility results in this direction were proved in \cite{dodis-renner}. \section*{Acknowledgement} We thank Ludwig Staiger for illuminating discussions on bi-immunity and stochasticity. %\if01 %From $X$ to the scenario of ``infinitely many quantum random bit-strings''. R. Dobrushin: ``infinity is a better approximation to Avogadro's number $6.0 \times 10^{23}$ than to the number 100''. %\fi %\bibliography{svozil} %\bibliographystyle{osa} %\bibliographystyle{apsrev} %\bibliographystyle{elsart-harv} %\bibliographystyle{unsrt} %\bibliographystyle{plain} \begin{thebibliography}{10} \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{jammer:66} M.~Jammer, \emph{The Conceptual Development of Quantum Mechanics} (McGraw-Hill Book Company, New York, 1966). \bibitem{jammer1} M.~Jammer, \emph{The Philosophy of Quantum Mechanics} (John Wiley \& Sons, New York, 1974). \bibitem{lakatosch} I.~Lakatos, \emph{Philosophical Papers. 1.~The Methodology of Scientific Research Programmes} (Cambridge University Press, Cambridge, 1978). \bibitem{bell-66} J.~S. Bell, \enquote{On the Problem of hidden variables in quantum mechanics,} Reviews of Modern Physics \textbf{38}, 447--452 (1966). Reprinted in \cite[pp. 1-13]{bell-87}, \urlprefix\url{http://dx.doi.org/10.1103/RevModPhys.38.447}. \bibitem{bell} J.~S. Bell, \enquote{On the {E}instein {P}odolsky {R}osen paradox,} Physics \textbf{1}, 195--200 (1964). Reprinted in \cite[pp. 403-408]{wheeler-Zurek:83} and in \cite[pp. 14-21]{bell-87}. \bibitem{bell-87} J.~S. Bell, \emph{Speakable and Unspeakable in Quantum Mechanics} (Cambridge University Press, Cambridge, 1987). \bibitem{pitowsky-89a} I.~Pitowsky, \enquote{From {G}eorge {B}oole to {J}ohn {B}ell: The origin of {B}ell's inequality,} in \emph{{B}ell's Theorem, Quantum Theory and the Conceptions of the Universe}, M.~Kafatos, ed., pp. 37--49 (Kluwer, Dordrecht, 1989). \bibitem{kochen1} S.~Kochen and E.~P. Specker, \enquote{The Problem of Hidden Variables in Quantum Mechanics,} Journal of Mathematics and Mechanics \textbf{17}(1), 59--87 (1967). Reprinted in \cite[pp. 235--263]{specker-ges}. \bibitem{ghz} D.~M. Greenberger, M.~A. Horne, and A.~Zeilinger, \enquote{Going beyond Bell's theorem,} in \emph{Bell's Theorem, Quantum Theory, and Conceptions of the {U}niverse}, M.~Kafatos, ed., pp. 73--76 (Kluwer Academic Publishers, Dordrecht, 1989). \bibitem{ghsz} D.~M. Greenberger, M.~A. Horne, A.~Shimony, and A.~Zeilinger, \enquote{{B}ell's theorem without inequalities,} American Journal of Physics \textbf{58}, 1131--1143 (1990). \bibitem{panbdwz} J.-W. Pan, D.~Bouwmeester, M.~Daniell, H.~Weinfurter, and A.~Zeilinger, \enquote{Experimental test of quantum nonlocality in three-photon {G}reenberger-{H}orne-{Z}eilinger entanglement,} Nature \textbf{403}, 515--519 (2000). \bibitem{epr} A.~Einstein, B.~Podolsky, and N.~Rosen, \enquote{Can quantum-mechanical description of physical reality be considered complete?} Physical Review \textbf{47}, 777--780 (1935). \urlprefix\url{http://dx.doi.org/10.1103/PhysRev.47.777}. \bibitem{zeil-99} A.~Zeilinger, \enquote{A Foundational Principle for Quantum Mechanics,} Foundations of Physics \textbf{29}(4), 631--643 (1999). \urlprefix\url{http://dx.doi.org/10.1023/A:1018820410908}. \bibitem{zeil-bruk-02} {\v{C}}.~Brukner and A.~Zeilinger, \enquote{Information and fundamental elements of the structure of quantum theory,} in \emph{Time, Quantum and Information}, L.~Castell and O.~Ischebek, eds., pp. 323--355 (Springer, Berlin, 2003). \eprint{quant-ph/0212084}. \bibitem{svozil-qct} K.~Svozil, \enquote{The quantum coin toss---Testing microphysical undecidability,} Physics Letters A \textbf{143}, 433--437 (1990). \urlprefix\url{http://dx.doi.org/10.1016/0375-9601(90)90408-G}. \bibitem{zeilinger:qct} T.~Jennewein, U.~Achleitner, G.~Weihs, H.~Weinfurter, and A.~Zeilinger, \enquote{A Fast and Compact Quantum Random Number Generator,} Review of Scientific Instruments \textbf{71}, 1675--1680 (2000). \eprint{quant-ph/9912118}, \urlprefix\url{http://dx.doi.org/10.1063/1.1150518}. \bibitem{Cris04} C.~S.~Calude, \enquote{{A}lgorithmic randomness, quantum physics, and incompleteness,} in \emph{Proceedings of the Conference ``Machines, Computations and Universality'' (MCU'2004)}, M.~Margenstern, ed., pp. 1--17 (Lectures Notes in Comput. Sci. 3354, Springer, Berlin, 2005). \bibitem{gard-78} M.~Gardner, \enquote{White and brown music, fractal curves and one-over-$f$ fluctuations,} Scientific American \textbf{238}, 16--32 (1978). See also URL http://www.seriouscomposer.com/TDML/tdml.htm. \bibitem{jauch} J.~M. Jauch, \emph{Foundations of Quantum Mechanics} (Addison-Wesley, Reading, MA., 1968). \bibitem{calude:02} C.~Calude, \emph{Information and Randomness---An Algorithmic Perspective}, 2nd ed. (Springer, Berlin, 2002). \bibitem{Quantis} id~Quantique, \enquote{Quantis - Quantum Random Number Generators,} (2004). \urlprefix\url{http://www.idquantique.com}. \bibitem{calude-dinneen05} M.~J.~Dinneen, C.~S.~Calude, \enquote{Is quantum randomness algorithmic random? A preliminary attack,} in \emph{Proceedings of the 1st International Conference on Algebraic Informatics}, G.~R. S.~Bozapalidis, A.~Kalampakas, ed., pp. 195--196 (Aristotle University of Thessaloniki, 2005). \bibitem{stace} W.~T. Stace, \enquote{The Refutation of Realism,} in \emph{Readings in philosophical analysis}, H.~Feigl and W.~Sellars, eds. (Appleton--Century--Crofts, New York, 1949). Previously published in {\em Mind} {\bf 53}, 1934. \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{wright} R.~Wright, \enquote{Generalized urn models,} Foundations of Physics \textbf{20}, 881--903 (1990). \bibitem{svozil-ql} K.~Svozil, \emph{Quantum Logic} (Springer, Singapore, 1998). \bibitem{ZirlSchl-65} N.~Zierler and M.~Schlessinger, \enquote{Boolean embeddings of orthomodular sets and quantum logic,} Duke Mathematical Journal \textbf{32}, 251--262 (1965). \bibitem{Alda} V.~Alda, \enquote{On\/ {\rm 0-1} measures for projectors I,} Aplik. mate. \textbf{25}, 373--374 (1980). \bibitem{Alda2} V.~Alda, \enquote{On\/ {\rm 0-1} measures for projectors II,} Aplik. mate. \textbf{26}, 57--58 (1981). \bibitem{kamber64} F.~Kamber, \enquote{Die {S}truktur des {A}ussagenkalk{\"{u}}ls in einer physikalischen {T}heorie,} Nachr. Akad. Wiss. G{\"{o}}ttingen \textbf{10}, 103--124 (1964). \bibitem{kamber65} F.~Kamber, \enquote{Zweiwertige {W}ahrscheinlichkeitsfunktionen auf orthokomplement{\"{a}}ren {V}erb{\"{a}}nden,} Mathematische Annalen \textbf{158}, 158--196 (1965). \bibitem{peres222} A.~Peres, \enquote{Unperformed experiments have no results,} American Journal of Physics \textbf{46}, 745--747 (1978). \urlprefix\url{http://dx.doi.org/10.1119/1.11393}. \bibitem{krenn} G.~Krenn, \enquote{The Probabilistic Origin of {B}ell's Inequality,} in \emph{Proceedings of the Third International Workshop on Squeezed States and Uncertainty Relations, Maryland, August 10-13, 1993, NASA Conference publication Nr. 3270}, D.~Han, Y.~S. Kim, N.~H. Rubin, Y.~Shih, and W.~W. Zachary, eds., pp. 603--608 (NASA, Greenbelt, Maryland 20771, 1993). \bibitem{svozil-krenn} G.~Krenn and K.~Svozil, \enquote{Stronger-than-quantum correlations,} Foundations of Physics \textbf{28}(6), 971--984 (1998). \urlprefix\url{http://dx.doi.org/10.1023/A:1018821314465}. \bibitem{odi:99} P.~Odifreddi, \emph{Classical Recursion Theory, Vol. 2} (North-Holland, Amsterdam, 1999). \bibitem{DH} D.~H. R.~Downey, \emph{Algorithmic Randomness and Complexity} (Springer, Berlin, 2007). To appear. \bibitem{dodis-renner} Y.~Dodis and R.~Renner, \enquote{On the impossibility of extracting classical randomness using a quantum computer,} in \emph{ICALP 2006, Part II}, M.~Bugliese, B.~Preneel, V.~Sassone, and I.~Wegener, eds., pp. 204--215 (LNCS 4052, Springer, Heidelberg, 2006). \bibitem{wheeler-Zurek:83} J.~A. Wheeler and W.~H. Zurek, \emph{Quantum Theory and Measurement} (Princeton University Press, Princeton, 1983). \bibitem{specker-ges} E.~Specker, \emph{Selecta} (Birkh{\"{a}}user Verlag, Basel, 1990). \end{thebibliography} \end{document}