\documentclass[ aip, cha, amssymb ]{revtex4-1} %\newcommand{\dom}{{\rm dom}} %\usepackage{latexsym,url,amssymb} \usepackage{graphicx} \def \C{{\mathfrak C}} \def \N{{\mathbf N}} \def \R{{\mathbf R}} \newenvironment{Instruction}[2]% { % \newcommand{\Name}[1]{\item[\hskip \labelsep{} ] ##1}% \noindent {\bf #1 \hfill #2} \\[-2ex] \begin{flushright}\begin{minipage}{\textwidth} }% {\end{minipage} \end{flushright}} \newtheorem{thm}{Theorem} \newtheorem{cor}[thm]{Corollary} \newtheorem{fact}[thm]{Fact} \newtheorem{lem}[thm]{Lemma} \newtheorem{defn}[thm]{Definition} %\newtheorem{prop}[thm]{Proposition} \newtheorem{sch}[thm]{Scholium} \newenvironment{proof}{\trivlist \item[\hskip \labelsep{\bf Proof.}]}% Dineen's {{\hfill$\Box$}\endtrivlist} \begin{document} \sloppy \title{The Complexity of Proving Chaoticity and the Church-Turing Thesis} \author{Cristian S. Calude} \email{cristian@cs.auckland.ac.nz} \homepage{http://www.cs.auckland.ac.nz/~cristian} \affiliation{Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand} \author{Elena Calude} \email{e.calude@massey.ac.nz} \homepage{http://www.massey.ac.nz/~ecalude} \affiliation{Institute of Information and Mathematical Sciences, Massey University at Albany, Private Bag 102-904, North Shore MSC New Zealand} \author{Karl Svozil} \email{svozil@tuwien.ac.at} \homepage{http://tph.tuwien.ac.at/~svozil} \affiliation{Institute for Theoretical Physics, {\it Vienna} University of Technology, Wiedner Hauptstrasse 8-10/136, 1040 {\it Vienna}, Austria} \date{\today} \begin{abstract} Proving the chaoticity of some dynamical systems is equivalent to solving the hardest problems in mathematics. Conversely, classical physical systems may ``compute the hard or even the incomputable'' by measuring observables which correspond to computationally hard or even incomputable problems. \end{abstract} \pacs{05.45.Ac,05.45.Gg,02.10.Ab} \keywords{computability, $\Pi_{1}$--statement, logic, ZFC provability, low-dimensional chaos} \preprint{CDMTCS preprint nr. 384/2010} \maketitle {\bf The relationship between classical physical systems modeled by continua and their theory of computation is still not entirely settled. On the one hand, chaotic systems indicate that it might be ``computationally hard'' to formally prove many of their properties, in particular chaoticity. On the other hand, it might not be too unreasonable to speculate that such physical systems, due to their capabilities of utilizing the continuum, may be capable of performing tasks which are beyond the scope of universal Turing machines based on discrete entities. } \section{Introduction} Proving that a dynamical system is chaotic is an important problem in chaos theory~\cite{1985cfd..book.....F}. Despite causality~\cite{suppes-1993}, {\it virtually any ``interesting'' question about non-trivial dynamical systems appears to be undecidable}~\cite{Stewart-91}, but is there a way to mathematically prove {\it this statement?} Closely related is the question: {\it Is there a way to measure the difficulty of proving the chaoticity of a dynamical system?} There are only few ``bridges'' between chaotic dynamical systems and complexity theories, in particular algorithmic information theory~\cite{brudno2,crutchfield1,moore,gacs09}. The unpredictability of the systems studied in this article comes from a combination of chaoticity and a ``decision problem'' embedded in the system; the complexity of the ``decision problem'' (in the sense to be precisely described in the following section) may be arbitrarily large, including high incomputability. We shall show that ``proving the chaoticity of some dynamical systems'' amounts to ``solving the hardest problems in mathematics'' and {\it vice versa.} We will study a class of mathematical sentences called $\Pi_{1}$--statements. A sentence of the form $\pi = \forall n \, {\rm Pred} (n)$, where Pred is a computable predicate ($n$ is always a non-negative integer) is called a $\Pi_{1}$--{\em statement}. The Greek letter $\pi$ is used as a generic notation for such a statement; it has no relation with the famous constant $3.145\cdots$. Clearly, $\pi$ is true if and only if all instances of Pred, ${\rm Pred} (0), {\rm Pred} (1), \dots , {\rm Pred} (n), \dots$ are true. Every $\Pi_{1}$--statement is {\it finitely refutable} because a single false instance of Pred makes $\pi$ false. For example, $\forall n [n^{2} + 1 >0]$ is true, but $\forall n [2n+3 \mbox { is prime}]$ is false. We deal with formal proofs by using the Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC), the standard system for doing mathematics. So, we say that ``ZFC proves $\pi$'' in case there is a proof in ZFC for $\pi$. Da Costa, Doria \cite{dc-d91b} and da Costa, Doria and Amaral~\cite{dc-d93} have constructed a two-dimensional Hamiltonian system $\mathcal{H}$ --- a system of first-order differential equations which can be written in the form of Hamilton's equations, in which the Hamiltonian function represents the total energy of the system --- with the property that (formally) proving the existence of a Smale horseshoe in $\mathcal{H}$ is equivalent to (formally) proving Fermat's last theorem. Contrary to the opinion expressed in the above articles, it was shown that proving that the two-dimensional Hamiltonian system $\mathcal{H}$ has a Smale horseshoe has low complexity~\cite{ecalude-10} because Fermat's last theorem has a low complexity. As Fermat's last theorem is a $\Pi_{1}$--statement, {\it it is natural to ask whether the above results can be extended to any $\Pi_{1}$--statement.} In this note we show that to every $\Pi_{1}$--statement $\pi$ one can associate a dynamical system $\mathcal{H}_{\pi}$ such that proving in ZFC the chaoticity of $\mathcal{H}_{\pi}$ is equivalent to proving $\pi$ in ZFC. By applying the computational method~\cite{calude-elena-dinneen06,calude-elena-ec1,calude-elena-ec2} to $\Pi_{1}$--statements we show that there are dynamical systems whose ZFC proofs of their chaoticity are arbitrarily complex and there are chaotic systems for which ZFC cannot prove their chaoticity. The techniques are related to (i) the construction of a Poincar\'e box as a classical physical random number generator (akin to a quantum Born box), and (ii) the conceivable capability of classical physical systems to ``compute the hard or even the incomputable'' by measuring observables which correspond to computationally hard or even incomputable problems. \section{$\Pi_{1}$--statements and the complexity measure} In this section we present a complexity measure~\cite{calude-elena-dinneen06,calude-elena-ec1,calude-elena-ec2} for $\Pi_{1}$--statements %[i.e. statements of the form ``$\forall n \, {\rm Pred}(n)$'', %where Pred is a computable predicate] defined by means of register machine programs. We use a fixed ``universal formalism'' for programs, more precisely, a universal self-delimiting Turing machine $U$. The machine $U$ (which is fully described below) has to be {\it minimal} in the sense that none of its instructions can be simulated by a program for $U$ written with the remaining instructions. To every $\Pi_{1}$--statement $\pi = \forall m {\rm Pred} (m)$ we associate the algorithm $\Pi_{\rm Pred}=\inf\{n\,:\, {\rm Pred}(n) = \mbox{ false}\}$ which systematically searches for a counter-example for $\pi$. There are many programs (for $U$) which implement $\Pi_{\rm Pred}$; without loss of generality, any such program will be denoted also by $\Pi_{\rm Pred}$. Note that $ \pi \mbox{ is true iff } U(\Pi_{\rm Pred})$ never halts. The complexity (with respect to $U$) of a $\Pi_{1}$--statement $\pi$ is defined by the length of the smallest-length program (for $U$) $\Pi_{\rm Pred}$---defined as above---where minimization is calculated for all possible representations of $\pi$ as $\pi = \forall n {\rm Pred}(n)$: $C_{U}(\pi) = \min \{ |\Pi_{{\rm Pred}}| \,:\, \pi = \forall n {\rm Pred}(n)\}$. For $C_{U}$ it is irrelevant whether $\pi$ is known to be true or false. In particular, the program containing the single instruction halt is not a $\Pi_{{\rm Pred}}$ program, for any Pred. As the exact value of $C_{U}$ is not important ($C_{U}$ is incomputable), following a previous article by two of the Authors~\cite{calude-elena-ec2} we classify $\Pi_{1}$--statements into the following classes: $\C_{U,n} = \{\pi \,:\, \pi \mbox{ is a $\Pi_{1}$--statement}, C_{U}(\pi) \le n \mbox{ kbit} \}.$ (Recall that a kilobit (kbit or kb) is equal to $2^{10}$ bits.) We briefly describe the syntax and the semantics of a register machine language which implements a (natural) minimal universal prefix-free binary Turing machine $U$. Any register program (machine) uses a finite number of registers, each of which may contain an arbitrarily large non-negative integer. By default, all registers, named with a string of lower or upper case letters, are initialized to 0. Instructions are labeled by default with 0,1,2,\ldots The register machine instructions are listed below. Note that in all cases R2 and R3 denote either a register or a non-negative integer, while R1 must be a register. When referring to R we use, depending upon the context, either the name of register R or the non-negative integer stored in R. %\begin{Instruction}{~=R1,R2,R3}{ } {\bf ~=R1,R2,R3}: if the contents of R1 and R2 are equal, then the execution continues at the R3-th instruction of the program; if the contents of R1 and R2 are not equal, then execution continues with the next instruction in sequence, and, if the content of R3 is outside the scope of the program, then we have an illegal branch error. {\bf ~\&R1,R2}: the contents of register R1 is replaced by R2. {\bf ~+R1,R2}: the contents of register R1 is replaced by the sum of the contents of R1 and R2. {\bf ~!R1}: one bit is read into the register R1, so the contents of R1 becomes either 0 or 1; any attempt to read past the last data-bit results in a run-time error. {\bf ~\%}: this is the last instruction for each register machine program before the input data; it halts the execution in two possible states: either successfully halts or it halts with an under-read error. A {\em register machine program}\/ consists of a finite list of labeled instructions from the above list, with the restriction that the halt instruction appears only once, as the last instruction of the list. \if01 The input data (a binary string) follows immediately after the halt instruction. A program not reading the whole data or attempting to read past the last data-bit results in a run-time error. Some programs (such as the ones presented in this article) have no input data; these programs cannot halt with an under-read error. The instruction {\tt =R,R,n} is used for the unconditional jump to the $n$-th instruction of the program. For Boolean data types we use integers 0 = \verb|false| and 1 = \verb|true|. For longer programs it is convenient to distinguish between the main program and some sets of instructions called ``routines'' which perform specific tasks for another routine or the main program. The call and call-back of a routine are executed with unconditional jumps. \fi To compute an upper bound on the complexity of a $\Pi_{1}$--statement $\pi$ we need to compute the size in bits of the program $\Pi_{\rm \pi}$, so we need to uniquely code in binary the programs for $U$. To this aim we use a prefix-free coding as follows. Table~\ref{2010-pi1chaos-t1} enumerates the binary coding of special characters. \begin{table} \caption{Binary encoding of special characters (instructions and comma); $\varepsilon$ is the empty string.} \begin{center} $\begin{array}{ c c| c c} \hline\hline {\rm special } \,\,\, {\rm characters} & {\rm code} & {\rm instruction} & {\rm code}\\ \hline , & \varepsilon & + & 111 \\ \& & 01 & ! & 110 \\ = & 00 & \% & 100\\ \hline\hline \end{array} $ \end{center} \label{2010-pi1chaos-t1} \end{table} For registers we use the prefix-free regular code ${\rm code}_{1} = \{0^{|x|}1x \mid x\in\{0,1\}^{*}\}$. %Table~\ref{2010-pi1chaos-t2} contains the codes of the first 14 registers. The register names are chosen to optimize the length of the program, i.e.\ the most frequent registers have the smallest ${\rm code}_{1}$ length. \if01 \begin{table} \caption{Binary encoding of the first 14 registers.} \begin{center} $\begin{array}{|c|c||c|c|} \hline\hline {\rm register} & {\rm code}_{1} & {\rm register} & {\rm code}_{1} \\\hline {\rm R}_1 & 010 & {\rm R}_8 & 0001001\\ {\rm R}_2 & 011 & {\rm R}_9 & 0001010\\ {\rm R}_3 & 00100 & {\rm R}_{10} & 0001011\\ {\rm R}_4 & 00101 & {\rm R}_{11} & 0001100\\ {\rm R}_5 & 00110 & {\rm R}_{12} & 0001101\\ {\rm R}_6 & 00111 & {\rm R}_{13} & 0001110\\ {\rm R}_7 & 0001000 & {\rm R}_{14} & 0001111\\ \hline\hline \end{array}$ \end{center} \label{2010-pi1chaos-t2} \end{table} \fi %\if01 %\begin{center} %\[\begin{array}{|c|c||c|c||c|c||c|c|} %\hline %{\rm register} & {\rm code}_{1} & {\rm register} & {\rm code}_{1} & {\rm register} & {\rm code}_{1} & {\rm register} & {\rm code}_{1} \\\hline %{\rm R}_1 & 010 & {\rm R}_9 & 0001010 & {\rm R}_{17} & 000010010& {\rm R}_{25} & 000011010\\ \hline %{\rm R}_2 & 011 & {\rm R}_{10} & 0001011& {\rm R}_{18} & 000010011&{\rm R}_{26} & 000011011\\ \hline %{\rm R}_3 & 00100 &{\rm R}_{11} & 0001100 & {\rm R}_{19} & 000010100 & {\rm R}_{27} & 000011100\\ \hline %{\rm R}_4 & 00101 & {\rm R}_{12} & 0001101& {\rm R}_{20} & 000010101& {\rm R}_{28} & 000011101\\\hline %{\rm R}_5 & 00110 & {\rm R}_{13} & 0001110 & {\rm R}_{21} & 000010110& {\rm R}_{29} & 000011110\\\hline % %{\rm R}_6 & 00111 & {\rm R}_{14} & 0001111 & {\rm R}_{22} & 000010111& {\rm R}_{30} & 000011111\\\hline % %{\rm R}_7 & 0001000 &{\rm R}_{15} & 000010000 &{\rm R}_{23} & 000011000& %{\rm R}_{31} & 00000100000\\\hline % %{\rm R}_8 & 0001001 &{\rm R}_{16} & 000010001 & {\rm R}_{24} & 000011001& {\rm R}_{32} & 00000100001\\\hline %\end{array}\] %Table~2 %\end{center} %\fi For non-negative integers we use the prefix-free regular code ${\rm code}_{2} = \{1^{|x|}0x \mid x\in\{0,1\}^{*}\}$. \if01 Table~\ref{2010-pi1chaos-t3} contains the codes of the first 16 non-negative integers. \begin{table} \caption{Binary encoding of the first 16 non-negative integers.} \begin{center} $\begin{array}{|c|c||c|c||c|c||c|c|} \hline\hline {\rm integer} & {\rm code}_{2} & {\rm integer} & {\rm code}_{2} & {\rm integer} & {\rm code}_{2} & {\rm integer} & {\rm code}_{2}\\\hline 0 & 100 & 4 & 11010 & 8 & 1110010& 12 & 1110110\\ 1 & 101 & 5 & 11011& 9 & 1110011& 13 & 1110111\\ 2 & 11000 & 6 & 1110000 & 10 & 1110100 & 14 & 111100000\\ 3 & 11001 & 7 & 1110001 & 11 & 1110101& 15 & 111100001 \\\hline\hline\end{array}$ \end{center} \label{2010-pi1chaos-t3} \end{table} \fi The instructions are coded by self-delimiting binary strings as follows (see more details in Refs.~\cite{calude-elena-dinneen06,calude-elena-ec1,calude-elena-ec2}): \begin{itemize} \item[{\rm (i)}] {\tt \&R1,R2} is coded in two different ways, depending on R2 (we omit $\varepsilon$): $ 01{\rm code}_{1}({\rm R}1){\rm code}_{i}({\rm R}2),$ where $i=1$ if R2 is a register and $i=2$ if R2 is a non-negative integer. \item[{\rm (ii)}] {\tt +R1,R2} is coded in two different ways depending on R2: $111{\rm code}_{1}({\rm R}1){\rm code}_{i}({\rm R}2),$ where $i=1$ if R2 is a register and $i=2$ if R2 is a non-negative integer. \item[{\rm (iii)}] {\tt =R1,R2,R3} is coded in four different ways depending on the data types of R2 and R3: $00{\rm code}_{1}({\rm R}1){\rm code}_{i}({\rm R}2){\rm code}_{j}({\rm R}3),$ where $i=1$ if R2 is a register and $i=2$ if R2 is a non-negative integer, $j=1$ if R3 is a register and $j=2$ if R3 is a non-negative integer. \item[{\rm (iv)}] {\tt !R1} is coded by $110{\rm code}_{1}({\rm R1}).$ \item[{\rm (v)}] {\tt \%} is coded by $100.$ \end{itemize} For example, Goldbach's conjecture (included in Hilbert's eighth problem~\cite{hilbert-1900e}) states that { \it all positive even integers greater than two can be expressed as the sum of two primes.} The program $\Pi_{\rm Goldbach}$ listed in Table~\ref{2010-pi1-t2} gives the upper bound $C_{U}({\rm Goldbach}) \le 540$ which proves that the Goldbach conjecture is in the lowest class $\C_{U,1}$. \if01 \begin{verbatim} {\tt 0} {\tt =} {\tt a a 16 } {\tt 19} {\tt \&} {\tt c 22 } {\tt 1} {\tt \&} {\tt e 2 } {\tt 20} {\tt \&} {\tt a h } {\tt 2} {\tt \&} {\tt d 1 } {\tt 21} {\tt =} {\tt a a 1 } {\tt 3} {\tt =} {\tt a e c } {\tt 22} {\tt =} {\tt d 0 } {\tt 4} {\tt \&} {\tt d 0 } {\tt 23} {\tt \&} {\tt i 0 } {\tt 5} {\tt \&} {\tt f e } {\tt 24} {\tt \&} {\tt k h } {\tt 6} {\tt =} {\tt f a 13 } {\tt 25} {\tt =} {\tt k g 29 } {\tt 7} {\tt +} {\tt f 1 } {\tt 26} {\tt +} {\tt i 1 } {\tt 8} {\tt +} {\tt d 1 } {\tt 27} {\tt +} {\tt k 1 } {\tt 9} {\tt =} {\tt d e 11 } {\tt 28} {\tt =} {\tt a a 25 } {\tt 10} {\tt =} {\tt a a 6 } {\tt 29} {\tt \&} {\tt c 32 } {\tt 11} {\tt \&} {\tt d 0 } {\tt 30} {\tt \&} {\tt a i } {\tt 12} {\tt =} {\tt a a 6 } {\tt 31} {\tt =} {\tt a a 1 } {\tt 13} {\tt =} {\tt d 0 c } {\tt 32} {\tt =} {\tt d 0 35 } {\tt 14} {\tt +} {\tt e 1 } {\tt 33} {\tt +} {\tt g 2 } {\tt 15} {\tt =} {\tt a a 2 } {\tt 34} {\tt =} {\tt a a 17 } {\tt 16} {\tt \&} {\tt g 4 } {\tt 35} {\tt +} {\tt h 1 } {\tt 17} {\tt \&} {\tt h 2 } {\tt 36} {\tt =} {\tt a a 18 } {\tt 18} {\tt =} {\tt g h 38 } {\tt 37} {\tt \&} {\tt d 0 } \end{verbatim} \fi \begin{table} \begin{center} \begin{tabular}{ll|cll|cll|cll} {\rm 00:\quad \quad}&{\tt = a a 16 } $\quad$&$\quad$&{\rm 11:\quad} &{\tt \& d 0 } $\quad$&$\quad$& {\rm 22:\quad} &{\tt = d 0 35 } $\quad$&$\quad$& {\rm 33:\quad} &{\tt + g 2 } \\ {\rm 01:}&{\tt \& e 2 } && {\rm 12:} &{\tt = a a 6 } && {\rm 23:} &{\tt \& i 0 } & & {\rm 34:} &{\tt = a a 17 } \\ {\rm 02:}&{\tt \& d 1 } && {\rm 13:} &{\tt = d 0 c } && {\rm 24:} &{\tt \& k h } & & {\rm 35:} &{\tt + h 1 } \\ {\rm 03:}&{\tt = a e c } && {\rm 14:}&{\tt + e 1 } && {\rm 25:} &{\tt = k g 29 } & & {\rm 36:} &{\tt = a a 18 } \\ {\rm 04:}&{\tt \& d 0 } && {\rm 15:}&{\tt = a a 2 } && {\rm 26:} &{\tt + i 1 } & & {\rm 37:} &{\tt \& d 0 } \\ {\rm 05:}&{\tt \& f e } && {\rm 16:}&{\tt \& g 4 } && {\rm 27:} &{\tt + k 1 } & & {\rm 38:} &{\tt \% } \\ {\rm 06:}&{\tt = f a 13 } && {\rm 17:}&{\tt \& h 2 } && {\rm 28:} &{\tt = a a 25 } & & \\ {\rm 07:}&{\tt + f 1 } && {\rm 18:} &{\tt = g h 38 } && {\rm 29:} &{\tt \& c 32 } & & {\rm } &{\tt } \\ {\rm 08:}&{\tt + d 1 } && {\rm 19:} &{\tt \& c 22 } && {\rm 30:} &{\tt \& a i } & & {\rm } &{\tt } \\ {\rm 09:}&{\tt = d e 11 } && {\rm 20:} &{\tt \& a h } && {\rm 31:} &{\tt = a a 1 } && {\rm } &{\tt } \\ {\rm 10:}&{\tt = a a 6 } && {\rm 21:} &{\tt = a a 1 } && {\rm 32:\quad} &{\tt = d 0 35 } & & {\rm } &{\tt } \end{tabular} \end{center} \caption{\label{2010-pi1-t2} Program $\Pi_{\rm Goldbach}$ for the Goldbach conjecture.} \end{table} %\if01 %{\small %\begin{verbatim} %0 = a a 16 %1 & e 2 %2 & d 1 %3 = a e c %4 & d 0 %5 & f e %6 = f a 13 %7 + f 1 %8 + d 1 %9 = d e 11 %10 = a a 6 %11 & d 0 %12 = a a 6 %13 = d 0 c %14 + e 1 %15 = a a 2 %16 & g 4 %17 & h 2 %18 = g h 38 %19 & c 22 %20 & a h %21 = a a 1 %22 = d 0 %23 & i 0 %24 & k h %25 = k g 29 %26 + i 1 %27 + k 1 %28 = a a 25 %29 & c 32 %30 & a i %31 = a a 1 %32 = d 0 35 %33 + g 2 %34 = a a 17 %35 + h 1 %36 = a a 18 %37 & d 0 %38 % %\end{verbatim} %} %\fi \if01 \section{Richardson-Caviness-Wang lemma} Following Richardson~\cite{richardson68}, Caviness~\cite{321591} and Wang~\cite{wang} we fix a positive integer $n$, and denote by $\mathcal{E}_{n}$ a set of expressions representing real valued, partially defined functions of real variables and by $F(\mathcal{E}_{n})$ the set of functions represented by the expressions in $\mathcal{E}_{n}$. By $e(x_{1}, x_{2}, \ldots ,x_{n})$ we denote the function represented by the expression $e\in \mathcal{E}_{n}$. Let $\mu$ and ${\rm sign}$ be the expressions denoting two unary functions such that $\mu(x) = |x|,\, {\rm sign}(x) = 1$, for all $x\not= 0$. We assume that $\mathcal{E}_{n}$ is generated by: \begin{itemize} \item[{\rm (i)}] the rational numbers and $\pi$ as constant functions, \item[{\rm (ii)}] variables $x_{1}, x_{2}, \ldots ,x_{n}$, \item[{\rm (iii)}] the functions $\sin, \mu, {\rm sign}$, and \item[{\rm (iv)}] the operations of addition, subtraction, multiplication and composition. \end{itemize} In fact we can omit subtraction and $\pi$, cf. Ref.~\cite{wang,Laczkovich-2002}. Let $\mathcal{P}_{n}$ be the set of polynomials with integral coefficients in the variables $x_{1}, x_{2}, \ldots ,x_{n}$. Let $\N, \R$ denote the set of non-negative integers and reals, respectively. \begin{lem}\label{equiv} {\rm Ref.~\cite{richardson68,321591,wang} } For every polynomial $P(x_{1}, x_{2}, \ldots ,x_{n}) \in \mathcal{P}_{n}$ there exists $f_{P}(x_{1}, x_{2}, \ldots ,x_{n}) \in F(\mathcal{E}_{n})$ such that the following conditions are equivalent. \begin{itemize} \item[{\rm (i)}] $\exists x_{1}, x_{2}, \ldots ,x_{n} \in \N$: $P(x_{1}, x_{2}, \ldots ,x_{n})=0$. \item[{\rm (ii)}] $\exists x_{1}, x_{2}, \ldots ,x_{n} \in \R$: $f_{P}(x_{1}, x_{2}, \ldots ,x_{n})=0$. \item[{\rm (iii)}] $\exists x_{1}, x_{2}, \ldots ,x_{n} \in \R$: $f_{P}(x_{1}, x_{2}, \ldots ,x_{n})\le 1$. \end{itemize} \end{lem} \fi \section{Main results} We start with a result relating $\Pi_{1}$--statements and Hamiltonians. \begin{thm} \label{CC}Assume {\rm ZFC} is arithmetically sound, i.e.\ every statement {\rm ZFC} proves is true. Then, to each $\Pi_{1}$--statement $\pi= \forall m \, {\rm Pred}(m)$ one can effectively construct in the formal language of {\rm ZFC} a Hamiltonian system $\mathcal{H}_{\pi}$ such that {\rm ZFC} proves that the system $\mathcal{H}_{\pi}$ has a Smale horseshoe iff {\rm ZFC} proves $\pi$. \end{thm} We denote by $h$ and $k$ the Hamiltonian for the two-dimensional system with a Smale horseshoe as defined by Holmes and Marsden~\cite{Homes-Marsden-82} (their Example~4) and the Hamiltonian for the free particle, respectively. Clearly, the systems $h$ and $k$ can be represented in the formal language of ZFC. Define the Hamiltonian $ \mathcal{H}_{\pi}^{m}$ as a linear combination of $h,k$: \begin{eqnarray} \label{H} \mathcal{H}_{\pi}^{m} (q_{1}, \dots ,q_{n}, p_{1}, \dots ,p_{n}) & = & {\rm Pred}(m) \cdot h (q_{1}, \dots ,q_{n}, p_{1}, \dots ,p_{n})\\ & & + (1- {\rm Pred}(m))\cdot k(q_{1}, \dots ,q_{n}, p_{1}, \dots ,p_{n}).\nonumber \end{eqnarray} Fix a positive integer $i$. In view of (\ref{H}), $\mathcal{H}_{\pi}^{i}$ can be represented in the formal language of ZFC and $\mathcal{H}_{\pi}^{i} (q_{1}, \dots ,q_{n}, p_{1}, \dots ,p_{n})$ $ = h(q_{1}, \dots ,q_{n}, p_{1}, \dots ,p_{n})$ iff $\mbox{ ZFC proves } \pi $. In case the above equivalence holds true, $\mathcal{H}_{\pi}^{i} (q_{1}, \dots ,q_{n}, p_{1}, \dots ,p_{n}) = \mathcal{H}_{\pi}^{j} (q_{1}, \dots ,q_{n}, p_{1}, \dots ,p_{n})$, for all non-negative integers $i, j$, hence we can name each $\mathcal{H}_{\pi}^{t}$ by $\mathcal{H}_{\pi}$. We have shown that \\[-5ex] \begin{quote} $\mbox{ ZFC proves } \pi \mbox{ iff ZFC proves that } \mathcal{H}_{\pi} \mbox{ has a Smale horseshoe}$, \end{quote} hence ending the proof of Theorem~\ref{CC}. %\end{proof} If $\pi$ is true but unprovable in ZFC, then the equality $ \mathcal{H}_{\pi}^{i} (q_{1}, \dots ,q_{n}, p_{1}, \dots ,p_{n})$ $ = h(q_{1}, \dots ,q_{n}, p_{1}, \dots ,p_{n})$ is true but unprovable in ZFC. In case $\pi$ is the Fermat's last theorem, Theorem~\ref{CC} is exactly the result proved~\cite{dc-d91b,dc-d93}; our direct proof does not need the machinery involving Richardson lemma used in Ref.~\cite{dc-d91b,dc-d93}. Theorem~\ref{CC} can be applied to a variety of $\Pi_{1}$--statements including Goldbach's conjecture, Riemann's hypothesis, the four color theorem, and many others. \medskip We address now the complexity issue: How difficult is it to prove in ZFC that the system $\mathcal{H}_{\pi}$ in Equation~(\ref{H}) is chaotic? Using the complexity $C_{U}$ we can show that Fermat's last theorem and Goldbach's conjecture are in $\C_{U,1}$, the Riemann hypothesis is in $\C_{U,3}$, and the four color theorem is in $\C_{U,4}$~\cite{calude-elena-ec2,calude-elena-CE3,ecalude-09}; their corresponding dynamical systems produced by Theorem~\ref{CC} have the property that the complexity of its chaoticity proof is in the corresponding class. As for every natural $n$ there exists a natural $m_{n}$ such that $\C_{U,n} \subset \C_{U,m_{n}}$, it follows that, according to $C_{U}$, there exist arbitrarily complex $\Pi_{1}$--statements; hence proving the chaoticity of the system $\mathcal{H}_{\pi}$ can be arbitrarily complex. Finally, there are infinitely many true, but unprovable in ZFC, $\Pi_{1}$--statements $\pi$~\cite{cal-paun-83}, such that the corresponding systems $\mathcal{H}_{\pi}^{i}$ are chaotic but ZFC cannot prove their chaoticity. For example, from the negation of the halting problem for $U$ we get infinitely many $\Pi_{1}$-statements $\pi_{x} =$ ``$\forall n$ ($U(x)$ does not stop in time $n$)'' which are undecidable in ZFC. \section{Computational capabilities of chaotic motion} One of the intriguing possibilities of the aforementioned equivalences between certain statements in ZFC and chaotic motion is the hypothetical possibility to ``decide'' hard problems in ZFC or ``perform incomputable tasks'' by observing the corresponding chaos~\cite{Scarpellini-63,Stewart-91,dc-d93,Scarpellini-2003,Scarpellini-2003c}. Indeed, if such methods and procedures have an ``effective'' physical implementation, then, strictly speaking, the Church-Turing thesis identifying the informal notion of {\em computable algorithm} with {\em Turing computability}, or, equivalently, {\em recursive functions}, is too restricted and has to be adapted to the physical capacities~\cite{davis-58,rogers1,kreisel} (for a converse viewpoint restricting operations to strictly finitistic means, see Refs.~\cite{bridgman,gandy2,gandy1}). It is rather intriguing that, at least in this respect, the situation resembles the famous Einstein, Podolski and Rosen (EPR) argument~\cite{epr} for a possible ``incompleteness'' of quantum mechanics. According to EPR, whereas quantum theory does not allow complementary physical observables to simultaneously ``exist,'' experiment (augmented with counterfactual reasoning) allows for such ``elements of physical reality.'' In the case of chaotic systems, our present theory of computability, formalized by recursion theory, does not allow the ``execution'' of certain ``hard'' tasks; but the equivalent chaotic systems would perform just such tasks, sometimes with relative ease on the side of the experimenter. One example of such seemingly mismatch --- in the sense of EPR --- of computability theory and physical computation is the construction of ``oracles producing random bits,'' as discussed in the next section. \section{Poincar\'e box as physical random number generator} Chaotic systems can be used as a physical device for incomputability. In the ``extreme'' algorithmically incompressible case, a chaotic dynamical system can serve as a source of random bits; i.e., as a physical {\em random number generator} (RNG). This RNG can be conceptualized by enclosing a chaotic system in a ``black box'' with an output interface which communicates the consecutive physical states of the chaotic evolution~\cite{PhysRevLett.45.712} in a properly encoded symbolic form. In order for these, say, strings of bits, to be physically certified random, it is necessary to ascertain chaoticity; a property which relates to the proofs of chaoticity discussed above. This scenario can be elucidated by considering the shift map $\sigma$ (a form of generalized shift studied by Moore~\cite{moore}) which ``pushes'' up successive bits of the sequence $s=0.s_1s_2s_3\cdots$; i.e., $\sigma (s)= 0.s_2s_3s_4\cdots$, $\sigma (\sigma (s))= 0.s_3s_4s_5\cdots$, and so on. Suppose one starts with an initial ``measurement'' precision of, say, just one bit after the comma, indicated by a ``window of measurability;'' all other information ``beyond the first bit after the comma'' is hidden to the experimenter at this point. Consider an initial state represented by an algorithmically random real $s$. At first the experimenter records the first position $s_1$ of $s$, symbolized by $0.[[s_1]]s_2 s_3\cdots$, where the square brackets ``$[[~\cdots~]]$'' indicate the boundaries of the experimenter's sliding ``window of measurability.'' Successive iterations of the shift map ``bring up'' more and more bits of the initial sequence of $s$; i.e., $\sigma (s)$ yields $0.s_1[[s_2]]s_3s_4\cdots$, $\sigma (\sigma (s))$ yields $0.s_1 s_2[[s_3]]s_4s_5\cdots$, and in general $\sigma^{(i)} (s)$ yields $ 0.\cdots s_{i-1}s_{i}[[s_{i+1}]]s_{i+2}s_{i+3}\cdots$ after $i$ iterations of the shift map. Thus effectively, the algorithmic information content of $s$ ``unfolds'' at a rate of one bit per time cycle. If $s$ is algorithmically random, then (at least ideally) the empirical recording of its successive bits generates a random sequence (in the asymptotic limit). It is not totally unreasonable to conjecture that, with respect to algorithmic (hence also statistical) tests of randomness, {\em Poincar\'e boxes} {\em cannot} be differentiated from another type of physical RNGs termed {\em Born boxes}, which are based on quantum indeterminism (e.g., photons impinging on beam splitters and detectors~\cite{svozil-qct,rarity-94,zeilinger:qct,stefanov-2000,0256-307X-21-10-027,wang:056107,fiorentino:032334,svozil-2009-howto}). Considering the different physical origins of physical indeterminism exploited by the Poincar\'e and Born boxes --- in the first, classical case, indeterminism resides in the continuum, whereas in the second, quantum case, in the postulated~\cite{born-26-1,born-26-2,zeil-05_nature_ofQuantum,2008-cal-svo} irreducible randomness of certain individual outcomes involving photons --- why should the two physical RNG's perform equally from an algorithmic information theoretic~\cite{chaitin3,calude:02} point of view? Because, one could argue, both would produce (in the asymptotic regime) random strings with high probability. The Poincare box derives its random behavior from a {\em single, individual} initial value containing incompressible algorithmic information with probability one~\cite{brudno2,crutchfield1}, whereas the Born box utilizes {\em successive, independent} ideal coin tosses. Whether or not these speculations are justified or not only experiment can tell. So far, no empirical evidence either for or against the conjectured equivalence of Poincar\'e and Born boxes exist. It is not too difficult to ``construct'' a Poincar\'e box by utilizing a shift map which ``pumps'' up the bits of the binary representation of the initial value by one bit per (discrete iteration) cycle. Of course, assuring the physical representability of this extreme chaotic regime for concrete classical chaotic systems, might turn out to be a ``hard'' task; as has been argued above. With this proviso, and by further assuming that the initial value is some element of the continuum (in ZFC the ``selection'' of an initial value is guaranteed by the Axiom of Choice), the shift map is, at least asymptotically, capable of yielding a random number with probability one. \section{Summary and outlook} We have argued that every $\Pi_{1}$--statement $\pi$ can be associated with a dynamical system $\mathcal{H}_{\pi}$ such that ZFC proves the chaoticity of $\mathcal{H}_{\pi}$ iff ZFC proves $\pi$. Many ``hard''problems, such as, for example, the Riemann hypothesis and the four color theorem, are $\Pi_{1}$--statements. The computational method~\cite{calude-elena-dinneen06,calude-elena-ec1,calude-elena-ec2} has been applied to $\Pi_{1}$--statements, resulting in a complexity measure for proving the chaoticity of some dynamical systems. Consequently, there are dynamical systems for which the ZFC proofs of their chaoticity are arbitrarily complex according to the above complexity measure. Furthermore, there are infinitely many chaotic systems for which ZFC cannot prove their chaoticity. One of the challenging conceptual questions which is motivated by these results is the issue of relating physical entities to formal ones. In particular at stake is the Church-Turing thesis, which is challenged from a classical physical perspective. As classical chaotic motion seems to be capable to ``perform'' incomputable tasks --- a criterion which might, as we argue, be ``hard'' to certify for a wide variety of Hamiltonian systems, but which nevertheless is a feasible scenario --- it might not be too unreasonable to speculate that the present formal theories of computability would have to be adapted in accordance with our physical capabilities originating from chaotic motion. \section*{Acknowledgement} We thank Alastair Abbott and the anonymous referees for critical comments which improved the article. %\bibliography{svozil} %merlin.mbs 2010-03-15 4.21a (PWD, AO, DPC) %Control: key (0) %Control: author (8) initials jnrlst %Control: editor formatted (1) identically to author %Control: production of article title (0) allowed %Control: page (1) range %Control: year (1) truncated %Control: production of eprint (0) enabled \begin{thebibliography}{44}% \makeatletter \providecommand \@ifxundefined [1]{% \@ifx{#1\undefined} }% \providecommand \@ifnum [1]{% \ifnum #1\expandafter \@firstoftwo \else \expandafter \@secondoftwo \fi }% \providecommand \@ifx [1]{% \ifx #1\expandafter \@firstoftwo \else \expandafter \@secondoftwo \fi }% \providecommand \natexlab [1]{#1}% \providecommand \enquote [1]{``#1''}% \providecommand \bibnamefont [1]{#1}% \providecommand \bibfnamefont [1]{#1}% \providecommand \citenamefont [1]{#1}% \providecommand \href@noop [0]{\@secondoftwo}% \providecommand \href [0]{\begingroup \@sanitize@url \@href}% \providecommand \@href[1]{\@@startlink{#1}\@@href}% \providecommand \@@href[1]{\endgroup#1\@@endlink}% \providecommand \@sanitize@url [0]{\catcode `\\12\catcode `\$12\catcode `\&12\catcode `\#12\catcode `\^12\catcode `\_12\catcode `\%12\relax}% \providecommand \@@startlink[1]{}% \providecommand \@@endlink[0]{}% \providecommand \url [0]{\begingroup\@sanitize@url \@url }% \providecommand \@url [1]{\endgroup\@href {#1}{\urlprefix }}% \providecommand \urlprefix [0]{URL }% \providecommand \Eprint [0]{\href }% \@ifxundefined \urlstyle {% \providecommand \doi [0]{\begingroup \@sanitize@url \@doi}% \providecommand \@doi [1]{\endgroup \@@startlink {\doibase #1}doi:\discretionary {}{}{}#1\@@endlink }% }{% \providecommand \doi [0]{doi:\discretionary{}{}{}\begingroup \urlstyle{rm}\Url }% }% \providecommand \doibase [0]{http://dx.doi.org/}% \providecommand \Doi [0]{\begingroup \@sanitize@url \@Doi }% \providecommand \@Doi [1]{\endgroup\@@startlink{\doibase#1}\@@Doi}% \providecommand \@@Doi [1]{#1\@@endlink}% \providecommand \selectlanguage [0]{\@gobble}% \providecommand \bibinfo [0]{\@secondoftwo}% \providecommand \bibfield [0]{\@secondoftwo}% \providecommand \translation [1]{[#1]}% \providecommand \BibitemOpen [0]{}% \providecommand \bibitemStop [0]{}% \providecommand \bibitemNoStop [0]{.\EOS\space}% \providecommand \EOS [0]{\spacefactor3000\relax}% \providecommand \BibitemShut [1]{\csname bibitem#1\endcsname}% % \bibitem [{\citenamefont {Hirsch}(1985)}]{1985cfd..book.....F}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Hirsch}},\ }\bibfield {title} {\enquote {\bibinfo {title} {The chaos of dynamical systems. {L}ecture notes in pure and applied mathematics. {V}olume~98},}\ }in\ \href@noop {} {\emph {\bibinfo {booktitle} {Chaos, fractals, and dynamics}}},\ \bibinfo {editor} {edited by\ \bibinfo {editor} {\bibfnamefont {P.}~\bibnamefont {Fischer}}\ and\ \bibinfo {editor} {\bibfnamefont {W.~R.}\ \bibnamefont {Smith}}}\ (\bibinfo {publisher} {M.~Dekker},\ \bibinfo {address} {New York},\ \bibinfo {year} {1985})\BibitemShut {NoStop}% \bibitem [{\citenamefont {Suppes}(1993)}]{suppes-1993}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {P.}~\bibnamefont {Suppes}},\ }\bibfield {title} {\enquote {\bibinfo {title} {The transcendental character of determinism},}\ }\Doi {10.1111/j.1475-4975.1993.tb00266.x} {\bibfield {journal} {\bibinfo {journal} {Midwest Studies In Philosophy},\ }\textbf {\bibinfo {volume} {18}},\ \bibinfo {pages} {242--257} (\bibinfo {year} {1993})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Stewart}(1991)}]{Stewart-91}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {I.}~\bibnamefont {Stewart}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Deciding the undecidable},}\ }\Doi {10.1038/352664a0} {\bibfield {journal} {\bibinfo {journal} {Nature},\ }\textbf {\bibinfo {volume} {352}},\ \bibinfo {pages} {664--665} (\bibinfo {year} {1991})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Brudno}(1983)}]{brudno2}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {A.~A.}\ \bibnamefont {Brudno}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Entropy and the complexity of the trajectories of a dynamical system},}\ }\href@noop {} {\bibfield {journal} {\bibinfo {journal} {Transactions of the Moscow Mathematical Society},\ }\textbf {\bibinfo {volume} {44}},\ \bibinfo {pages} {127--151} (\bibinfo {year} {1983})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Crutchfield}\ and\ \citenamefont {Packard}(1982)}]{crutchfield1}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {J.~P.}\ \bibnamefont {Crutchfield}}\ and\ \bibinfo {author} {\bibfnamefont {N.~H.}\ \bibnamefont {Packard}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise},}\ }\Doi {10.1007/BF02650178} {\bibfield {journal} {\bibinfo {journal} {International Journal of Theoretical Physics},\ }\textbf {\bibinfo {volume} {21}},\ \bibinfo {pages} {433--466} (\bibinfo {year} {1982})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Moore}(1990)}]{moore}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {C.~D.}\ \bibnamefont {Moore}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Unpredictability and undecidability in dynamical systems},}\ }\Doi {10.1103/PhysRevLett.64.2354} {\bibfield {journal} {\bibinfo {journal} {Physical Review Letters},\ }\textbf {\bibinfo {volume} {64}},\ \bibinfo {pages} {2354--2357} (\bibinfo {year} {1990})},\ \bibinfo {note} {cf. Ch. Bennett, {\sl Nature}, {\bf 346}, 606 (1990)}\BibitemShut {NoStop}% \bibitem [{\citenamefont {G\'acs}\ \emph {et~al.}(2009)\citenamefont {G\'acs}, \citenamefont {Hoyrup},\ and\ \citenamefont {Rojas}}]{gacs09}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {P.}~\bibnamefont {G\'acs}}, \bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Hoyrup}}, \ and\ \bibinfo {author} {\bibfnamefont {C.}~\bibnamefont {Rojas}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Randomness on computable probability spaces. {A} dynamical point of view},}\ }in\ \href {http://stacs2009.informatik.uni-freiburg.de/proceedings_stacs09.pdf} {\emph {\bibinfo {booktitle} {26th International Symposium on Theoretical Aspects of Computer Science - {STACS 2009}}}},\ \bibinfo {editor} {edited by\ \bibinfo {editor} {\bibfnamefont {S.}~\bibnamefont {Albers}}\ and\ \bibinfo {editor} {\bibfnamefont {J.-Y.}\ \bibnamefont {Marion}}}\ (\bibinfo {publisher} {IBFI Schloss Dagstuhl},\ \bibinfo {address} {Freiburg},\ \bibinfo {year} {2009})\ pp.\ \bibinfo {pages} {469--480},\ \Eprint {http://arxiv.org/abs/arXiv:0902.1939} {arXiv:0902.1939} \BibitemShut {NoStop}% \bibitem [{\citenamefont {{da Costa}}\ and\ \citenamefont {Doria}(1991)}]{dc-d91b}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {N.~C.~A.}\ \bibnamefont {{da Costa}}}\ and\ \bibinfo {author} {\bibfnamefont {F.~A.}\ \bibnamefont {Doria}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Undecidability and incompleteness in classical mechanics},}\ }\Doi {10.1007/BF00671484} {\bibfield {journal} {\bibinfo {journal} {International Journal of Theoretical Physics},\ }\textbf {\bibinfo {volume} {30}},\ \bibinfo {pages} {1041--1073} (\bibinfo {year} {1991})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {{da Costa}}\ \emph {et~al.}(1993)\citenamefont {{da Costa}}, \citenamefont {Doria},\ and\ \citenamefont {do~Amaral}}]{dc-d93}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {N.~C.~A.}\ \bibnamefont {{da Costa}}}, \bibinfo {author} {\bibfnamefont {F.~A.}\ \bibnamefont {Doria}}, \ and\ \bibinfo {author} {\bibfnamefont {A.~F.~F.}\ \bibnamefont {do~Amaral}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Dynamical system where proving chaos is equivalent to proving {F}ermat's conjecture},}\ }\Doi {10.1007/BF00675030} {\bibfield {journal} {\bibinfo {journal} {International Journal of Theoretical Physics},\ }\textbf {\bibinfo {volume} {32}},\ \bibinfo {pages} {2187--2206} (\bibinfo {year} {1993})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Calude}(2010)}]{ecalude-10}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {E.}~\bibnamefont {Calude}},\ }\href {http://www.cs.auckland.ac.nz/CDMTCS/researchreports/383elena.pdf} {\enquote {\bibinfo {title} {{F}ermat's last theorem and chaoticity},}\ } (\bibinfo {year} {2010}),\ \bibinfo {note} {{CDMTCS} preprint 383}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Calude}\ \emph {et~al.}(2006)\citenamefont {Calude}, \citenamefont {Calude},\ and\ \citenamefont {Dinneen}}]{calude-elena-dinneen06}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {C.~S.}\ \bibnamefont {Calude}}, \bibinfo {author} {\bibfnamefont {E.}~\bibnamefont {Calude}}, \ and\ \bibinfo {author} {\bibfnamefont {M.~J.}\ \bibnamefont {Dinneen}},\ }\bibfield {title} {\enquote {\bibinfo {title} {A new measure of the difficulty of problems},}\ }\href {http://www.cs.auckland.ac.nz/CDMTCS/researchreports/277cris.pdf} {\bibfield {journal} {\bibinfo {journal} {Journal for Multiple-Valued Logic and Soft Computing},\ }\textbf {\bibinfo {volume} {12}},\ \bibinfo {pages} {285--307} (\bibinfo {year} {2006})},\ \bibinfo {note} {{CDMTCS} report series 277}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Calude}\ and\ \citenamefont {Calude}(2009)}]{calude-elena-ec1}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {C.~S.}\ \bibnamefont {Calude}}\ and\ \bibinfo {author} {\bibfnamefont {E.}~\bibnamefont {Calude}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Evaluating the complexity of mathematical problems. {P}art 1},}\ }\href {http://www.complex-systems.com/pdf/18-3-1.pdf} {\bibfield {journal} {\bibinfo {journal} {Complex Systems},\ }\textbf {\bibinfo {volume} {19}},\ \bibinfo {pages} {267--285} (\bibinfo {year} {2009})},\ \bibinfo {note} {{CDMTCS} report series 343}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Calude}\ and\ \citenamefont {Calude}(2010)}]{calude-elena-ec2}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {C.~S.}\ \bibnamefont {Calude}}\ and\ \bibinfo {author} {\bibfnamefont {E.}~\bibnamefont {Calude}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Evaluating the complexity of mathematical problems. {P}art 2},}\ }\href {http://www.cs.auckland.ac.nz/CDMTCS//researchreports/369cris.pdf} {\bibfield {journal} {\bibinfo {journal} {Complex Systems},\ }\textbf {\bibinfo {volume} {18}},\ \bibinfo {pages} {387--401} (\bibinfo {year} {2010})},\ \bibinfo {note} {{CDMTCS} report series 369}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Hilbert}(1902)}]{hilbert-1900e}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {D.}~\bibnamefont {Hilbert}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Mathematical problems},}\ }\Doi {10.1090/S0002-9904-1902-00923-3} {\bibfield {journal} {\bibinfo {journal} {Bull. Amer. Math. Soc.},\ }\textbf {\bibinfo {volume} {8}},\ \bibinfo {pages} {437--479} (\bibinfo {year} {1902})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Holmes}\ and\ \citenamefont {Marsden}(1982)}]{Homes-Marsden-82}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {P.~J.}\ \bibnamefont {Holmes}}\ and\ \bibinfo {author} {\bibfnamefont {J.~E.}\ \bibnamefont {Marsden}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Horseshoes in perturbations of {H}amiltonian systems with two degrees of freedom},}\ }\Doi {10.1007/BF01961239} {\bibfield {journal} {\bibinfo {journal} {Communications in Mathematical Physics},\ }\textbf {\bibinfo {volume} {82}},\ \bibinfo {pages} {523--544} (\bibinfo {year} {1982})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Calude}\ and\ \citenamefont {Calude}()}]{calude-elena-CE3}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {C.~S.}\ \bibnamefont {Calude}}\ and\ \bibinfo {author} {\bibfnamefont {E.}~\bibnamefont {Calude}},\ }\bibfield {title} {\enquote {\bibinfo {title} {The complexity of the four colour theorem},}\ }\href {http://www.cs.auckland.ac.nz/CDMTCS//researchreports/368cris.pdf} {\bibfield {journal} {\bibinfo {journal} {LMS Journal of Computation and Mathematics}},\ }\bibinfo {note} {in print, CDMTCS Research Report 368}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Calude}(2009)}]{ecalude-09}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {E.}~\bibnamefont {Calude}},\ }\href {http://www.cs.auckland.ac.nz/CDMTCS/researchreports/370elena.pdf} {\enquote {\bibinfo {title} {The complexity of the {G}oldbach's conjecture and {R}iemann's hypothesis},}\ } (\bibinfo {year} {2009}),\ \bibinfo {note} {{CDMTCS} preprint 370}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Calude}\ and\ \citenamefont {P\u{a}un}(1983)}]{cal-paun-83}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {C.}~\bibnamefont {Calude}}\ and\ \bibinfo {author} {\bibfnamefont {G.}~\bibnamefont {P\u{a}un}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Independent instances for some undecidable problems},}\ }\href@noop {} {\bibfield {journal} {\bibinfo {journal} {RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)},\ }\textbf {\bibinfo {volume} {17}},\ \bibinfo {pages} {49--54} (\bibinfo {year} {1983})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Scarpellini}(1963)}]{Scarpellini-63}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {B.}~\bibnamefont {Scarpellini}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Zwei unentscheidbare {P}robleme der {A}nalysis},}\ }\Doi {10.1002/malq.19630091802} {\bibfield {journal} {\bibinfo {journal} {Zeitschrift f{\"{u}}r Mathematische Logik und Grundlagen der Mathematik},\ }\textbf {\bibinfo {volume} {9}},\ \bibinfo {pages} {265--289} (\bibinfo {year} {1963})},\ ISSN \bibinfo {issn} {1521-3870}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Scarpellini}(2003){\natexlab{a}}}]{Scarpellini-2003}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {B.}~\bibnamefont {Scarpellini}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Two undecidable problems of analysis},}\ }\Doi {http://dx.doi.org/10.1023/A:1021381032553} {\bibfield {journal} {\bibinfo {journal} {Minds and Machines},\ }\textbf {\bibinfo {volume} {13}},\ \bibinfo {pages} {49--77} (\bibinfo {year} {2003}{\natexlab{a}})},\ ISSN \bibinfo {issn} {0924-6495}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Scarpellini}(2003){\natexlab{b}}}]{Scarpellini-2003c}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {B.}~\bibnamefont {Scarpellini}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Comments on `two undecidable problems of analysis'},}\ }\Doi {http://dx.doi.org/10.1023/A:1021364916624} {\bibfield {journal} {\bibinfo {journal} {Minds and Machines},\ }\textbf {\bibinfo {volume} {13}},\ \bibinfo {pages} {79--85} (\bibinfo {year} {2003}{\natexlab{b}})},\ ISSN \bibinfo {issn} {0924-6495}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Davis}(1958)}]{davis-58}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Davis}},\ }\href@noop {} {\emph {\bibinfo {title} {Computability and Unsolvability}}}\ (\bibinfo {publisher} {McGraw-Hill},\ \bibinfo {address} {New York},\ \bibinfo {year} {1958})\BibitemShut {NoStop}% \bibitem [{\citenamefont {{Rogers, Jr.}}(1967)}]{rogers1}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {H.}~\bibnamefont {{Rogers, Jr.}}},\ }\href@noop {} {\emph {\bibinfo {title} {Theory of Recursive Functions and Effective Computability}}}\ (\bibinfo {publisher} {MacGraw-Hill},\ \bibinfo {address} {New York},\ \bibinfo {year} {1967})\BibitemShut {NoStop}% \bibitem [{\citenamefont {Kreisel}(1974)}]{kreisel}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {G.}~\bibnamefont {Kreisel}},\ }\bibfield {title} {\enquote {\bibinfo {title} {A notion of mechanistic theory},}\ }\Doi {10.1007/BF00484949} {\bibfield {journal} {\bibinfo {journal} {Synthese},\ }\textbf {\bibinfo {volume} {29}},\ \bibinfo {pages} {11--26} (\bibinfo {year} {1974})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Bridgman}(1934)}]{bridgman}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {P.~W.}\ \bibnamefont {Bridgman}},\ }\bibfield {title} {\enquote {\bibinfo {title} {A physicist's second reaction to {M}engenlehre},}\ }\href@noop {} {\bibfield {journal} {\bibinfo {journal} {Scripta Mathematica},\ }\textbf {\bibinfo {volume} {2}},\ \bibinfo {pages} {101--117, 224--234} (\bibinfo {year} {1934})},\ \bibinfo {note} {cf. R. Landauer \cite{landauer-95}}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Gandy}(1980)}]{gandy2}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {R.~O.}\ \bibnamefont {Gandy}},\ }\bibfield {title} {\enquote {\bibinfo {title} {{C}hurch's thesis and principles for mechanics},}\ }in\ \href@noop {} {\emph {\bibinfo {booktitle} {The {K}leene Symposium. {V}ol. 101 of Studies in Logic and Foundations of Mathematics}}},\ \bibinfo {editor} {edited by\ \bibinfo {editor} {\bibfnamefont {J.}~\bibnamefont {Barwise}}, \bibinfo {editor} {\bibfnamefont {H.~J.}\ \bibnamefont {Kreisler}}, \ and\ \bibinfo {editor} {\bibfnamefont {K.}~\bibnamefont {Kunen}}}\ (\bibinfo {publisher} {North Holland},\ \bibinfo {address} {Amsterdam},\ \bibinfo {year} {1980})\ pp.\ \bibinfo {pages} {123--148}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Gandy}(1982)}]{gandy1}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {R.~O.}\ \bibnamefont {Gandy}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Limitations to mathematical knowledge},}\ }in\ \href@noop {} {\emph {\bibinfo {booktitle} {Logic Colloquium '82}}},\ \bibinfo {editor} {edited by\ \bibinfo {editor} {\bibfnamefont {D.}~\bibnamefont {van Dalen}}, \bibinfo {editor} {\bibfnamefont {D.}~\bibnamefont {Lascar}}, \ and\ \bibinfo {editor} {\bibfnamefont {J.}~\bibnamefont {Smiley}}}\ (\bibinfo {publisher} {North Holland},\ \bibinfo {address} {Amsterdam},\ \bibinfo {year} {1982})\ p.\ \bibinfo {pages} {129–146}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Einstein}\ \emph {et~al.}(1935)\citenamefont {Einstein}, \citenamefont {Podolsky},\ and\ \citenamefont {Rosen}}]{epr}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {A.}~\bibnamefont {Einstein}}, \bibinfo {author} {\bibfnamefont {B.}~\bibnamefont {Podolsky}}, \ and\ \bibinfo {author} {\bibfnamefont {N.}~\bibnamefont {Rosen}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Can quantum-mechanical description of physical reality be considered complete?}}\ }\Doi {10.1103/PhysRev.47.777} {\bibfield {journal} {\bibinfo {journal} {Physical Review},\ }\textbf {\bibinfo {volume} {47}},\ \bibinfo {pages} {777--780} (\bibinfo {year} {1935})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Packard}\ \emph {et~al.}(1980)\citenamefont {Packard}, \citenamefont {Crutchfield}, \citenamefont {Farmer},\ and\ \citenamefont {Shaw}}]{PhysRevLett.45.712}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {N.~H.}\ \bibnamefont {Packard}}, \bibinfo {author} {\bibfnamefont {J.~P.}\ \bibnamefont {Crutchfield}}, \bibinfo {author} {\bibfnamefont {J.~D.}\ \bibnamefont {Farmer}}, \ and\ \bibinfo {author} {\bibfnamefont {R.~S.}\ \bibnamefont {Shaw}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Geometry from a time series},}\ }\Doi {10.1103/PhysRevLett.45.712} {\bibfield {journal} {\bibinfo {journal} {Physical Review Letters},\ }\textbf {\bibinfo {volume} {45}},\ \bibinfo {pages} {712--716} (\bibinfo {year} {1980})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Svozil}(1990)}]{svozil-qct}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {K.}~\bibnamefont {Svozil}},\ }\bibfield {title} {\enquote {\bibinfo {title} {The quantum coin toss---testing microphysical undecidability},}\ }\Doi {10.1016/0375-9601(90)90408-G} {\bibfield {journal} {\bibinfo {journal} {Physics Letters A},\ }\textbf {\bibinfo {volume} {143}},\ \bibinfo {pages} {433--437} (\bibinfo {year} {1990})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Rarity}\ \emph {et~al.}(1994)\citenamefont {Rarity}, \citenamefont {Owens},\ and\ \citenamefont {Tapster}}]{rarity-94}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {J.~G.}\ \bibnamefont {Rarity}}, \bibinfo {author} {\bibfnamefont {M.~P.~C.}\ \bibnamefont {Owens}}, \ and\ \bibinfo {author} {\bibfnamefont {P.~R.}\ \bibnamefont {Tapster}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Quantum random-number generation and key sharing},}\ }\Doi {10.1080/09500349414552281} {\bibfield {journal} {\bibinfo {journal} {Journal of Modern Optics},\ }\textbf {\bibinfo {volume} {41}},\ \bibinfo {pages} {2435--2444} (\bibinfo {year} {1994})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Jennewein}\ \emph {et~al.}(2000)\citenamefont {Jennewein}, \citenamefont {Achleitner}, \citenamefont {Weihs}, \citenamefont {Weinfurter},\ and\ \citenamefont {Zeilinger}}]{zeilinger:qct}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {T.}~\bibnamefont {Jennewein}}, \bibinfo {author} {\bibfnamefont {U.}~\bibnamefont {Achleitner}}, \bibinfo {author} {\bibfnamefont {G.}~\bibnamefont {Weihs}}, \bibinfo {author} {\bibfnamefont {H.}~\bibnamefont {Weinfurter}}, \ and\ \bibinfo {author} {\bibfnamefont {A.}~\bibnamefont {Zeilinger}},\ }\bibfield {title} {\enquote {\bibinfo {title} {A fast and compact quantum random number generator},}\ }\Doi {10.1063/1.1150518} {\bibfield {journal} {\bibinfo {journal} {Review of Scientific Instruments},\ }\textbf {\bibinfo {volume} {71}},\ \bibinfo {pages} {1675--1680} (\bibinfo {year} {2000})},\ \Eprint {http://arxiv.org/abs/quant-ph/9912118} {quant-ph/9912118} \BibitemShut {NoStop}% \bibitem [{\citenamefont {Stefanov}\ \emph {et~al.}(2000)\citenamefont {Stefanov}, \citenamefont {Gisin}, \citenamefont {Guinnard}, \citenamefont {Guinnard},\ and\ \citenamefont {Zbinden}}]{stefanov-2000}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {A.}~\bibnamefont {Stefanov}}, \bibinfo {author} {\bibfnamefont {N.}~\bibnamefont {Gisin}}, \bibinfo {author} {\bibfnamefont {O.}~\bibnamefont {Guinnard}}, \bibinfo {author} {\bibfnamefont {L.}~\bibnamefont {Guinnard}}, \ and\ \bibinfo {author} {\bibfnamefont {H.}~\bibnamefont {Zbinden}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Optical quantum random number generator},}\ }\Doi {10.1080/095003400147908} {\bibfield {journal} {\bibinfo {journal} {Journal of Modern Optics},\ }\textbf {\bibinfo {volume} {47}},\ \bibinfo {pages} {595--598} (\bibinfo {year} {2000})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Hai-Qiang}\ \emph {et~al.}(2004)\citenamefont {Hai-Qiang}, \citenamefont {Su-Mei}, \citenamefont {Da}, \citenamefont {Jun-Tao}, \citenamefont {Ling-Ling}, \citenamefont {Yan-Xue},\ and\ \citenamefont {Ling-An}}]{0256-307X-21-10-027}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Hai-Qiang}}, \bibinfo {author} {\bibfnamefont {W.}~\bibnamefont {Su-Mei}}, \bibinfo {author} {\bibfnamefont {Z.}~\bibnamefont {Da}}, \bibinfo {author} {\bibfnamefont {C.}~\bibnamefont {Jun-Tao}}, \bibinfo {author} {\bibfnamefont {J.}~\bibnamefont {Ling-Ling}}, \bibinfo {author} {\bibfnamefont {H.}~\bibnamefont {Yan-Xue}}, \ and\ \bibinfo {author} {\bibfnamefont {W.}~\bibnamefont {Ling-An}},\ }\bibfield {title} {\enquote {\bibinfo {title} {A random number generator based on quantum entangled photon pairs},}\ }\Doi {10.1088/0256-307X/21/10/027} {\bibfield {journal} {\bibinfo {journal} {Chinese Physics Letters},\ }\textbf {\bibinfo {volume} {21}},\ \bibinfo {pages} {1961--1964} (\bibinfo {year} {2004})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Wang}\ \emph {et~al.}(2006)\citenamefont {Wang}, \citenamefont {Long},\ and\ \citenamefont {Li}}]{wang:056107}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {P.~X.}\ \bibnamefont {Wang}}, \bibinfo {author} {\bibfnamefont {G.~L.}\ \bibnamefont {Long}}, \ and\ \bibinfo {author} {\bibfnamefont {Y.~S.}\ \bibnamefont {Li}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Scheme for a quantum random number generator},}\ }\Doi {10.1063/1.2338830} {\bibfield {journal} {\bibinfo {journal} {Journal of Applied Physics},\ }\textbf {\bibinfo {volume} {100}},\ \bibinfo {eid} {056107} (\bibinfo {year} {2006})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Fiorentino}\ \emph {et~al.}(2007)\citenamefont {Fiorentino}, \citenamefont {Santori}, \citenamefont {Spillane}, \citenamefont {Beausoleil},\ and\ \citenamefont {Munro}}]{fiorentino:032334}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Fiorentino}}, \bibinfo {author} {\bibfnamefont {C.}~\bibnamefont {Santori}}, \bibinfo {author} {\bibfnamefont {S.~M.}\ \bibnamefont {Spillane}}, \bibinfo {author} {\bibfnamefont {R.~G.}\ \bibnamefont {Beausoleil}}, \ and\ \bibinfo {author} {\bibfnamefont {W.~J.}\ \bibnamefont {Munro}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Secure self-calibrating quantum random-bit generator},}\ }\Doi {10.1103/PhysRevA.75.032334} {\bibfield {journal} {\bibinfo {journal} {Physical Review A (Atomic, Molecular, and Optical Physics)},\ }\textbf {\bibinfo {volume} {75}},\ \bibinfo {eid} {032334} (\bibinfo {year} {2007})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Svozil}(2009)}]{svozil-2009-howto}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {K.}~\bibnamefont {Svozil}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Three criteria for quantum random-number generators based on beam splitters},}\ }\Doi {10.1103/PhysRevA.79.054306} {\bibfield {journal} {\bibinfo {journal} {Physical Review A (Atomic, Molecular, and Optical Physics)},\ }\textbf {\bibinfo {volume} {79}},\ \bibinfo {eid} {054306} (\bibinfo {year} {2009})},\ \Eprint {http://arxiv.org/abs/arXiv:0903.2744} {arXiv:0903.2744} \BibitemShut {NoStop}% \bibitem [{\citenamefont {Born}(1926){\natexlab{a}}}]{born-26-1}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Born}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Zur {Q}uantenmechanik der {S}to{\ss}vorg{\"{a}}nge},}\ }\Doi {10.1007/BF01397477} {\bibfield {journal} {\bibinfo {journal} {Zeitschrift f{\"{u}}r Physik},\ }\textbf {\bibinfo {volume} {37}},\ \bibinfo {pages} {863--867} (\bibinfo {year} {1926}{\natexlab{a}})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Born}(1926){\natexlab{b}}}]{born-26-2}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Born}},\ }\bibfield {title} {\enquote {\bibinfo {title} {{Q}uantenmechanik der {S}to{\ss}vorg{\"{a}}nge},}\ }\Doi {10.1007/BF01397184} {\bibfield {journal} {\bibinfo {journal} {Zeitschrift f{\"{u}}r Physik},\ }\textbf {\bibinfo {volume} {38}},\ \bibinfo {pages} {803--827} (\bibinfo {year} {1926}{\natexlab{b}})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Zeilinger}(2005)}]{zeil-05_nature_ofQuantum}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {A.}~\bibnamefont {Zeilinger}},\ }\bibfield {title} {\enquote {\bibinfo {title} {The message of the quantum},}\ }\Doi {10.1038/438743a} {\bibfield {journal} {\bibinfo {journal} {Nature},\ }\textbf {\bibinfo {volume} {438}},\ \bibinfo {pages} {743} (\bibinfo {year} {2005})}\BibitemShut {NoStop}% \bibitem [{\citenamefont {Calude}\ and\ \citenamefont {Svozil}(2008)}]{2008-cal-svo}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {C.~S.}\ \bibnamefont {Calude}}\ and\ \bibinfo {author} {\bibfnamefont {K.}~\bibnamefont {Svozil}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Quantum randomness and value indefiniteness},}\ }\Doi {10.1166/asl.2008.016} {\bibfield {journal} {\bibinfo {journal} {Advanced Science Letters},\ }\textbf {\bibinfo {volume} {1}},\ \bibinfo {pages} {165--168} (\bibinfo {year} {2008})},\ \Eprint {http://arxiv.org/abs/arXiv:quant-ph/0611029} {arXiv:quant-ph/0611029} \BibitemShut {NoStop}% \bibitem [{\citenamefont {Chaitin}(1987)}]{chaitin3}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {G.~J.}\ \bibnamefont {Chaitin}},\ }\href {http://www.cs.auckland.ac.nz/~chaitin/cup.pdf} {\emph {\bibinfo {title} {Algorithmic Information Theory}}}\ (\bibinfo {publisher} {Cambridge University Press},\ \bibinfo {address} {Cambridge},\ \bibinfo {year} {1987})\BibitemShut {NoStop}% \bibitem [{\citenamefont {Calude}(2002)}]{calude:02}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {C.}~\bibnamefont {Calude}},\ }\href@noop {} {\emph {\bibinfo {title} {Information and Randomness---An Algorithmic Perspective}}},\ \bibinfo {edition} {2nd}\ ed.\ (\bibinfo {publisher} {Springer},\ \bibinfo {address} {Berlin},\ \bibinfo {year} {2002})\BibitemShut {NoStop}% \bibitem [{\citenamefont {Landauer}(1994)}]{landauer-95}% \BibitemOpen \bibfield {author} {\bibinfo {author} {\bibfnamefont {R.}~\bibnamefont {Landauer}},\ }\bibfield {title} {\enquote {\bibinfo {title} {Advertisement for a paper {I} like},}\ }in\ \href {http://www.santafe.edu/research/publications/workingpapers/94-10-056.pdf} {\emph {\bibinfo {booktitle} {On Limits}}},\ \bibinfo {editor} {edited by\ \bibinfo {editor} {\bibfnamefont {J.~L.}\ \bibnamefont {Casti}}\ and\ \bibinfo {editor} {\bibfnamefont {J.~F.}\ \bibnamefont {Traub}}}\ (\bibinfo {publisher} {Santa Fe Institute Report 94-10-056},\ \bibinfo {address} {Santa Fe, NM},\ \bibinfo {year} {1994})\ p.~\bibinfo {pages} {39}\BibitemShut {NoStop}% \end{thebibliography}% \end{document}